Quicksort

Quicksort picks one element as the pivot, then rearranges the array so every element smaller than the pivot ends up to its left and every element larger ends up to its right. The pivot is now in its final sorted position. Recursing on the left and right sub-arrays finishes the sort.

Unlike merge sort, which does its real work in the combine step after the recursion, quicksort does its real work in the partition step before the recursion — the array is already substantially sorted by the time the recursive calls happen.

function partition(nums, low, high) {
  const pivot = nums[high];   // choose the last element as pivot
  let i = low - 1;

  for (let j = low; j < high; j++) {
    if (nums[j] < pivot) {
      i++;
      [nums[i], nums[j]] = [nums[j], nums[i]];
    }
  }
  [nums[i + 1], nums[high]] = [nums[high], nums[i + 1]];
  return i + 1; // final index of the pivot
}

Partitioning n elements takes a single O(n) pass, exactly like merge sort’s merge step.

function quicksort(nums, low = 0, high = nums.length - 1) {
  if (low < high) {
    const pivotIndex = partition(nums, low, high);
    quicksort(nums, low, pivotIndex - 1);
    quicksort(nums, pivotIndex + 1, high);
  }
  return nums;
}

If the pivot lands roughly in the middle of the range each time, the array splits into two halves of comparable size — the same balanced-recursion-tree shape as merge sort: O(n) partition work per level, O(log n) levels, O(n log n) total. This holds on average across random inputs, even though no single partition is guaranteed to split exactly in half.

The risk is entirely about how unbalanced the partition is. If the pivot is always the smallest or largest remaining element — which happens on already-sorted or reverse-sorted input when the pivot is chosen as the first or last element — each partition step only removes one element from consideration instead of roughly half:

• Partition call 1: n elements, O(n) work, leaves n − 1
• Partition call 2: n − 1 elements, O(n − 1) work, leaves n − 2
• …and so on down to 1

That’s n + (n − 1) + (n − 2) + … + 1, which sums to O(n²) — and instead of O(log n) recursion depth, you get O(n) depth, one level per element.

The entire best/worst-case gap comes down to how the pivot is chosen:

• First or last element: simplest to implement, but degrades to O(n²) on already-sorted or reverse-sorted input — a realistic case, not just an adversarial one.
• Random element: makes the worst case astronomically unlikely for any specific input, since an attacker would need to predict the random choices to construct a bad case.
• Median-of-three (first, middle, last — take the median): cheap to compute and reliably avoids the sorted-input worst case without the overhead of finding a true median.

None of these strategies change the average-case complexity — they only change how likely you are to hit the worst case in practice.

Space complexity here is recursion-stack depth, not auxiliary storage — the partition step rearranges elements in place. Balanced partitions give O(log n) stack depth; the fully unbalanced worst case gives O(n) depth, one stack frame per element.

Both are O(n log n) on average with the same divide-and-conquer shape, but they trade off differently:

• Worst case: merge sort guarantees O(n log n) always; quicksort can degrade to O(n²) on bad input or bad pivot choice.
• Space: quicksort sorts in place with O(log n) auxiliary space (call stack only); merge sort needs O(n) auxiliary space for the merge step.
• Practice:quicksort is usually faster in practice due to better cache locality and lower constant factors, which is why it’s the default in many standard library sort implementations — with safeguards like random or median-of-three pivots to avoid the worst case.

Sorting [10, 7, 8, 9, 1, 5] with the last element as pivot:

• Partition [10, 7, 8, 9, 1, 5], pivot = 5: elements less than 5 → just [1]. Result: [1, 5, 8, 9, 10, 7], pivot 5 now at index 1.
• Left of pivot: [1] — already sorted (base case).
• Right of pivot, partition [8, 9, 10, 7], pivot = 7: nothing is less than 7. Result: [7, 9, 10, 8], pivot 7 now at index 0 of this sub-range.
• Right of that pivot, partition [9, 10, 8], pivot = 8: nothing less than 8. Result: [8, 10, 9], pivot 8 placed, recurse on [10, 9] → [9, 10].
• Final result: [1, 5, 7, 8, 9, 10]

• Big-O Cheat Sheet — see where O(n log n) and O(n²) rank among the other complexity classes.
• How to Analyze Time Complexity of Any Algorithm — the general method behind the average/worst-case reasoning above.
• Space Complexity Explained — more on why quicksort’s recursion stack costs O(log n) to O(n).
• Merge Sort — the guaranteed-O(n log n) alternative, at the cost of O(n) auxiliary space.