Quicksort and the pivot problem

Quicksort picks a pivot, partitions the array so smaller elements sit left and larger right, then recurses into each side. Unlike merge sort, the work happens before the recursion, and no merge is needed.

function quickSort(a, lo = 0, hi = a.length - 1) {
  if (lo >= hi) return a;

  const p = partition(a, lo, hi);
  quickSort(a, lo, p - 1);
  quickSort(a, p + 1, hi);
  return a;
}

// Lomuto partition: simple to write, easy to reason about.
function partition(a, lo, hi) {
  // Random pivot, swapped to the end — this is the line that avoids O(n²).
  const r = lo + Math.floor(Math.random() * (hi - lo + 1));
  [a[r], a[hi]] = [a[hi], a[r]];

  const pivot = a[hi];
  let i = lo;

  for (let j = lo; j < hi; j++) {
    if (a[j] < pivot) { [a[i], a[j]] = [a[j], a[i]]; i++; }
  }

  [a[i], a[hi]] = [a[hi], a[i]];
  return i;
}

The pivot decides everything

A pivot near the median splits the array evenly: log n levels, O(n log n) total. A pivot at the extreme peels off one element per level: n levels, O(n²).

Choosing the first element as pivot makes already sorted input the worst case — the input you are most likely to be handed. Fixes, in order of common use:

1. Random pivot — makes the worst case improbable rather than input-dependent.
2. Median of three — first, middle and last; cheap and effective in practice.
3. Introsort — track recursion depth and switch to heapsort past a threshold, giving a hard O(n log n) ceiling. This is what C++ std::sort does.

Duplicates

Lomuto partition degrades to O(n²) on arrays with many equal keys. Three-way partitioning (Dutch national flag) splits into less-than, equal, greater-than and handles duplicates in linear time. Worth knowing by name.

Quicksort versus merge sort

Recurse into the smaller side first and loop on the larger, and the stack stays O(log n) even on a bad split.