Comparison Based vs Non Comparison Based Sorting in DSA C++ - Complexity Comparison

Time Complexity: Comparison Based vs Non Comparison Based Sorting

O(n^2) for comparison based, O(n + k) for non comparison based

Understanding Time Complexity

Sorting is a common task, and how fast it runs depends on the method used.

We want to see how time grows when sorting gets bigger with different sorting types.

Scenario Under Consideration

Analyze the time complexity of these two sorting approaches.

// Comparison based sorting example (Bubble Sort)
void bubbleSort(int arr[], int n) {
  for (int i = 0; i < n - 1; i++) {
    for (int j = 0; j < n - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        std::swap(arr[j], arr[j + 1]);
      }
    }
  }
}

// Non-comparison based sorting example (Counting Sort)
void countingSort(int arr[], int n, int maxVal) {
  int count[maxVal + 1] = {0};
  for (int i = 0; i < n; i++) count[arr[i]]++;
  int index = 0;
  for (int i = 0; i <= maxVal; i++) {
    while (count[i]-- > 0) arr[index++] = i;
  }
}
    

Bubble Sort compares elements repeatedly; Counting Sort counts occurrences to sort.

Identify Repeating Operations

Look at the loops and repeated steps in each method.

• Bubble Sort primary operation: Comparing and swapping pairs inside nested loops.
• Bubble Sort how many times: About n x n times (nested loops).
• Counting Sort primary operation: Counting each element once, then placing them back.
• Counting Sort how many times: Counting loop runs n times; placement loop runs maxVal times.

How Execution Grows With Input

See how operations increase as input size grows.

Input Size (n)	Bubble Sort Ops (approx.)	Counting Sort Ops (approx.)
10	100	10 + maxVal
100	10,000	100 + maxVal
1000	1,000,000	1000 + maxVal

Bubble Sort grows very fast (square of n), Counting Sort grows mostly with n plus max value range.

Final Time Complexity

Time Complexity: O(n²) for comparison based (Bubble Sort), O(n + k) for non comparison based (Counting Sort)

Bubble Sort gets much slower as n grows; Counting Sort depends on n and the range of values (k).

Common Mistake

[X] Wrong: "All sorting methods take about the same time because they all sort the list."

[OK] Correct: Some methods compare items many times, others use counting or special tricks that can be faster depending on data.

Interview Connect

Knowing these differences helps you pick the right sorting method and explain your choice clearly in interviews.

Self-Check

"What if the input values are very large but n is small? How would Counting Sort's time complexity be affected?"