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.
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.
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 ten comparison sorts on this site — including when a worst-case guarantee matters more than typical-case speed — see Choosing a Comparison Sort.