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.
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.
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.
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;
}
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.
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.
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.
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.