Sorting Stability and When to Use Which Sort in DSA Javascript - Time & Space Complexity

Time Complexity: Sorting Stability and When to Use Which Sort

O(n^2) for Bubble Sort, O(n log n) average for Quick Sort

Understanding Time Complexity

Sorting is a common task where we arrange items in order. Knowing how long different sorting methods take helps us pick the best one.

We want to understand how the time to sort grows as the list gets bigger and when to choose each sort.

Scenario Under Consideration

Analyze the time complexity of these sorting methods.

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

// Example: Quick Sort (unstable)
function quickSort(arr) {
  if (arr.length <= 1) return arr;
  const pivot = arr[arr.length - 1];
  const left = arr.filter(x => x < pivot);
  const right = arr.filter(x => x > pivot);
  const equal = arr.filter(x => x === pivot);
  return [...quickSort(left), ...equal, ...quickSort(right)];
}
    

Bubble Sort is stable and simple but slower; Quick Sort is faster on average but unstable.

Identify Repeating Operations

Look at the loops and recursive calls that repeat work.

• Bubble Sort: Nested loops comparing and swapping elements repeatedly.
• Quick Sort: Recursive calls splitting the array and filtering elements.
• Dominant operation: Comparisons and swaps in Bubble Sort; recursive splits and filtering in Quick Sort.

How Execution Grows With Input

As the list grows, Bubble Sort does many more comparisons, while Quick Sort splits the list efficiently.

Input Size (n)	Approx. Operations Bubble Sort	Approx. Operations Quick Sort
10	~100 (10*10)	~30 (10 log 10)
100	~10,000 (100*100)	~700 (100 log 100)
1000	~1,000,000 (1000*1000)	~10,000 (1000 log 1000)

Bubble Sort grows much faster, roughly by the square of input size; Quick Sort grows slower, roughly input size times log of input size.

Final Time Complexity

Time Complexity: O(n²) for Bubble Sort, O(n log n) average for Quick Sort

Bubble Sort takes much longer as the list grows, while Quick Sort is faster but can be slower in the worst case.

Common Mistake

[X] Wrong: "Faster sorting always means stable sorting."

[OK] Correct: Some fast sorts like Quick Sort are unstable, meaning equal items can change order, which matters in some cases.

Interview Connect

Understanding when to use stable or unstable sorts and their time costs shows you know how to pick the right tool for the job, a key skill in coding interviews.

Self-Check

"What if we used Merge Sort instead of Quick Sort? How would the time complexity and stability change?"