Cairn
algorithms · sorting · O(n log n) average

↩ back to Comparison Sorts

Quicksort

Quicksort takes the same divide-and-conquer bet as merge sort, but pays for it differently. Instead of splitting the array in half by position and doing the hard work on the way back up (the merge), quicksort does the hard work on the way down: pick a pivot, then partition the array so everything smaller than the pivot ends up to its left and everything larger ends up to its right. The pivot is now in its final sorted position — nothing left to do to it, ever again — so you recurse on the two sides independently, and never need to merge anything back together.

Try it

Enter a comma-separated list of numbers, pick a pivot strategy, then step through the sort. The dashed box is the active partition window; the solid accent bar is the current pivot. When the strategy picks something other than the window's last element, you'll see an extra step where it gets swapped into place first — after that, partitioning always proceeds the same way, scanning left to right and swapping anything smaller than the pivot into the shaded "confirmed smaller" region. Once the sweep finishes, the pivot swaps into the boundary between the two regions — that's its final resting place — and the window splits in two for the next round. Paste in 1,2,3,4,5,6,7,8 under "last element" to watch the worst case happen, then switch strategy and reload the same input to see it not happen.

Press Load, then Step through the sort.

Why it works

The invariant is on the partition, not the merge: after partitioning around a pivot, every element left of it is ≤ the pivot and every element right of it is ≥ the pivot. That means the pivot's index in the partitioned array is exactly where it belongs in the fully sorted array — recursing on [lo..pivotIndex-1] and [pivotIndex+1..hi] independently is guaranteed to produce a correct sort, because nothing in the left recursion can ever need to cross into the right, or vice versa. Unlike merge sort, there's no separate combine step: by the time both recursive calls return, the array is already sorted in place.

Reference implementation

The classic Lomuto partition scheme, choosing the last element of each range as the pivot — the same scheme the demo above steps through by default (last-element pivot), not a simplified stand-in. Switching the demo's pivot dropdown only changes which index gets swapped to hi before this runs — the partition logic itself is untouched:

function quickSort(arr, lo = 0, hi = arr.length - 1) {
  if (lo >= hi) return arr;
  const p = partition(arr, lo, hi);
  quickSort(arr, lo, p - 1);
  quickSort(arr, p + 1, hi);
  return arr;
}

function partition(arr, lo, hi) {
  const pivot = arr[hi];
  let i = lo - 1;
  for (let j = lo; j < hi; j++) {
    if (arr[j] < pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]];
    }
  }
  [arr[i + 1], arr[hi]] = [arr[hi], arr[i + 1]];
  return i + 1;
}

Pitfalls

Worst case is O(n²), and it's not exotic input that triggers it. This scheme always picks the last element as pivot. Feed it an already-sorted (or reverse-sorted) array and every partition splits into a range of size n-1 and a range of size 0 — the recursion depth becomes O(n) instead of O(log n), and total work becomes O(n²). Real-world implementations dodge this by picking the pivot differently: a random index, the median of three sampled elements, or (for library sorts) switching strategy entirely once a bad pattern is detected — see introsort for the specific hybrid that this describes, and heap sort's Pitfalls for why heap sort is the fallback it switches to. The demo above defaults to the plain last-element rule specifically so you can paste in 1,2,3,4,5,6,7,8 and watch the worst case happen — switch the pivot dropdown to try the same input against the other two.

Neither alternative eliminates the worst case, they just make it very unlikely to hit by accident. Random pivot selection has no single input that reliably triggers O(n²) — the bad case depends on the random draws, not the data, so the same sorted array that breaks last-element selection every time will, on average, split roughly evenly. But "average" is doing real work in that sentence: an unlucky run can still draw a bad pivot every level, it's just vanishingly improbable rather than impossible. Median-of-three is deterministic, not random, which means it necessarily has its own worst-case input — specific interleavings (sometimes called "median-of-three killer" sequences) are constructed precisely so that the low/middle/high sample is always the same badly-skewed element. It takes more engineering to construct than "already sorted," which is why median-of-three is considered a strong practical default despite this — but "strong practical default" and "asymptotically solved" are different claims, and this page only makes the first one.

Measure it instead of taking the comparison on faith. This race runs the exact partition logic above — the only change is an explicit stack instead of recursion, so an already-sorted array's degenerate n-deep recursion can't blow the call stack at the sizes below — for all three pivot strategies, on a freshly generated array, and counts every arr[j] < pivot comparison. No timing: at these sizes all three finish in a few milliseconds, too fast for performance.now() to clear JIT noise reliably.

Press "Run race" to count real comparisons for all three pivot strategies on the same array.

At n = 5,000, already sorted: last-element pivoting makes exactly 12,497,500 comparisons — precisely n(n-1)/2, the signature of a range that only ever shrinks by one element per partition — while median-of-three makes 51,822 and random pivoting lands close to it, both near the n log₂ n ≈ 61,439 reference line. That's roughly 241× fewer comparisons from switching pivot strategy alone, on an input shape (already sorted, or re-sorted after a small edit) that's common, not adversarial.

Switch to reverse sorted and random pivoting barely moves, but median-of-three gets measurably worse: 100,346 comparisons at the same n = 5,000 — nearly double its own sorted-case number, and above the n log₂ n line. The top-level pivot choice isn't the problem: the first partition still lands dead center, splitting 5,000 elements into two ranges of roughly 2,500. The problem is what the Lomuto scan leaves behind — finding the first element smaller than the pivot deep inside a descending range drags one small value all the way to the front of the left partition, leaving the rest in close to their original descending order. That new range is nearly reverse-sorted again, so the next level's three-sample degrades the same way, and the imbalance compounds level after level. Not last-element's O(n²) collapse on the same input — this stays O(n log n) — but a real, measured cost from ordinary data, no adversarial "killer" construction required.

It's not stable. The Lomuto swap moves elements across long distances in a single step, with no guarantee that two equal elements keep their original relative order — contrast with merge sort, where the <= comparison in the merge step preserves it deliberately. If you need a stable sort, quicksort isn't it without extra bookkeeping.

The recursion is on partition boundaries, not array halves. A common mistake when implementing this from memory is to recurse on [lo..p] and [p..hi] (inclusive of the pivot's index on both sides) instead of excluding it — that reprocesses the pivot forever and either infinite-loops or produces wrong output. The pivot is done the moment partition places it; neither recursive call should ever touch that index again.

Measuring against Merge Sort

The Complexity section below calls this page's in-place partitioning "a smaller, faster constant in the common case" against merge sort's guaranteed bound — true, but unquantified until measured. Rather than reimplement either algorithm from scratch, this instruments the exact quickSort/partition functions shown above and merge sort's own shipped mergeSort/merge functions directly, counting every comparison (arr[j] < pivot here, left[i] <= right[j] there) and timing wall-clock on random arrays of 1,000 through 1,000,000 numbers, averaged across repeated trials with sort order alternated trial to trial to cancel out any cache-warming bias.

The comparison counts actually favor merge sort, not quicksort: at n = 1,000 this page's last-element-pivot partitioning makes about 26% more comparisons than merge sort (≈11,000 vs ≈8,700), widening to about 32% more at n = 1,000,000 (≈24.7M vs ≈18.7M) — the cost of never finding the perfect halfway split that merge sort's position-based division gets for free every time. But wall-clock time runs the opposite direction, and by a much larger margin: merge sort takes roughly 2.3x longer at n = 10,000, widening to roughly 2.7x longer at n = 1,000,000 (n = 1,000 is too fast for either to time reliably above JIT noise, same caveat as the pivot race above). Raw comparison count is the wrong proxy for the real cost here: merge sort's arr.slice() calls and out.push() builds allocate a brand new array at every level of the recursion, while quicksort's partition swaps two elements in the same array and allocates nothing. More comparisons, fewer allocations, and quicksort still wins decisively — the claim above holds, and now by how much.

Complexity

Time: O(n log n) average case — a good pivot splits the range roughly in half, giving log n levels each doing O(n) total partitioning work, same shape as merge sort's recurrence. Worst case is O(n²) (see Pitfalls). Space: O(log n) average for the recursion stack — no merge buffers, because partitioning happens in place. That smaller memory footprint, and better cache behavior from working within one array rather than allocating new ones at every level, is why quicksort (or a hybrid built on it, like introsort) backs the unstable sort in most standard libraries — C++'s std::sort, and historically Java's Arrays.sort for primitives — trading merge sort's guaranteed bound for a smaller, faster constant in the common case.

For how this fits against the other eleven comparison sorts on this site — including when a worst-case guarantee matters more than typical-case speed — see Choosing a Comparison Sort. The random-pivot variant above always sorts correctly and only gambles on running time — see Las Vegas vs. Monte Carlo for how that differs from an algorithm that gambles on correctness instead. See How Deep Can You Recurse? for how far past "slow" the same worst-case input actually goes — far enough to exhaust the real call stack outright, not just run slowly. The fixed-pivot version's 241×-at-n=5,000 slowdown above is this site's clearest example of a permanent worst case — see Graceful Degradation vs. Cliffs for how that differs from the random-pivot version's own, strictly safer, probabilistic one.