Comparison Based vs Non Comparison Based Sorting in DSA Javascript - Complexity Comparison

Time Complexity: Comparison Based vs Non Comparison Based Sorting

O(n²) for comparison based, O(n + k) for non comparison based

Understanding Time Complexity

Sorting is a common task where we arrange items in order. Different sorting methods take different times depending on how they work.

We want to understand how the time to sort grows as the list gets bigger.

Scenario Under Consideration

Analyze the time complexity of these two sorting approaches.

// Comparison based sorting example (Bubble Sort)
function bubbleSort(arr) {
  for (let i = 0; i < arr.length; i++) {
    for (let j = 0; j < arr.length - i - 1; j++) {
      if (arr[j] > arr[j + 1]) {
        [arr[j], arr[j + 1]] = [arr[j + 1], arr[j]];
      }
    }
  }
  return arr;
}

// Non-comparison based sorting example (Counting Sort)
function countingSort(arr, max) {
  const count = new Array(max + 1).fill(0);
  for (let num of arr) count[num]++;
  let index = 0;
  for (let i = 0; i < count.length; i++) {
    while (count[i]-- > 0) {
      arr[index++] = i;
    }
  }
  return arr;
}
    

Bubble Sort compares elements to sort, Counting Sort uses counts without direct comparisons.

Identify Repeating Operations

Look at the loops and repeated steps in each method.

• Bubble Sort: Two nested loops comparing pairs of elements.
• Counting Sort: One loop to count, one loop to rebuild the array.
• Dominant operation: Bubble Sort's nested comparisons dominate time.

How Execution Grows With Input

As the list size grows, how does the work increase?

Input Size (n)	Bubble Sort Ops (approx.)	Counting Sort Ops (approx.)
10	~100 comparisons	~10 counts + 10 rebuild
100	~10,000 comparisons	~100 counts + 100 rebuild
1000	~1,000,000 comparisons	~1000 counts + 1000 rebuild

Bubble Sort grows much faster (square of n), Counting Sort grows roughly linearly with n.

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 list grows; Counting Sort stays faster if numbers are in a small range.

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 tricks that can be much faster for certain data.

Interview Connect

Knowing how sorting methods differ helps you choose the right tool and explain your choices clearly in interviews.

Self-Check

What if the input numbers for Counting Sort were very large? How would that affect its time complexity?