Quicksort

The problem it solves

Sorting is the most-run algorithm family on earth, and quicksort is, for in-memory arrays, usually the one actually running. It sorts in place — no second array — with sequential memory access patterns that caches love, and average-case O(n log n) with constants small enough that fifty years of challengers have mostly failed to displace it. When a language’s standard sort says “introsort” or “pattern-defeating quicksort” in the fine print, that is quicksort with a safety net.

What it trades away: a worst case of O(n²) if pivots are chosen badly, and stability — equal elements can end up reordered, which matters when sorting by one key after another. Those two trades define exactly when to reach for merge sort instead.

The intuition — and where it breaks down

Sorting a bookshelf, you might grab one book — say, one starting with “M” — and shove everything earlier in the alphabet to its left, everything later to its right. You haven’t sorted anything yet, except: that one book is now exactly where it will stand when the shelf is finished. Everything left of it belongs left; everything right belongs right; the M-book never moves again. Now do the same to each side, independently, and each round plants more books in their final positions until every book is one.

That’s a partition: one element (the pivot) placed permanently, the rest merely classified. The insight that makes quicksort fast is that classification is cheap — one comparison per element, done with a single scan — and it buys you two strictly smaller problems.

Where the analogy breaks: you’d naturally pick a middle-ish book, and your judgment is decent. The algorithm can’t eyeball the shelf — it must choose a pivot by rule, and an adversarial input can make any fixed rule terrible. Pick the first element on an already-sorted shelf and every “partition” peels off a single book: n rounds of n work. The bookshelf never fights back; real inputs do.

Loading…

A walkthrough you can check

Partition [7, 2, 9, 4, 6] with pivot 6 (moved to the end): scan with a store index starting at 0, swapping anything smaller than 6 into the store position.

1. 7 — not smaller. Store stays 0.
2. 2 < 6 — swap into index 0. Array: [2, 7, 9, 4, 6], store 1.
3. 9 — not smaller.
4. 4 < 6 — swap into index 1. Array: [2, 4, 9, 7, 6], store 2.
5. Scan done: swap the pivot into the store. Array: [2, 4, 6, 7, 9] — and 6 is at index 2 forever, because exactly two elements are smaller than it.

That last sentence is the prediction the visualization asks you to make: before the partition runs, you can compute the pivot’s landing spot by counting the elements smaller than it. Nothing else about the partition’s output is guaranteed — [4, 2] on the left would have been equally valid — only the pivot’s position is final.

The invariant

During a partition: everything left of store is strictly smaller than the pivot; everything from store up to the scan pointer is at least the pivot. After it: the pivot at store is in its final sorted position — the guarantee that makes the recursion terminate, since every call permanently places at least one element.

The recursion-level invariant is worth saying in an interview: at any moment, the array is a set of disjoint unsorted ranges separated by elements already in final position — and those separators are sorted with respect to everything, not just their neighbours.

Complexity, derived

Each level of recursion partitions disjoint ranges covering (almost) the whole array — about n comparisons per level. The number of levels is the depth of the recursion: with balanced partitions, ranges halve, so ~log₂ n levels and n log n total. With worst-case pivots, ranges shrink by one, n levels, n² total. The whole game is pivot quality, which is why the implementation here uses median-of-three: on sorted input — the classic killer — first, middle and last bracket the true median, and the trace’s max-stack-depth counter stays logarithmic (there’s a test asserting it).

The subtler duplicate-keys problem: with many equal elements, a two-way partition sends “equal to pivot” all one way, unbalancing every split. The few-unique preset in the input editor demonstrates the comparison count climbing; three-way partitioning (Dutch national flag) fixes it by fencing off the equal block and recursing on strictly-smaller and strictly-larger only — on all-equal input that’s O(n) flat.

Space is the recursion stack: O(log n) if you recurse on the smaller side and loop on the larger, O(n) if you recurse blindly on both. Interviewers ask this precisely because most people have never thought about it.

What people get wrong

Claiming randomized pivots “fix” the worst case. They make it vanishingly unlikely per run, which is different from gone — and on adversarial inputs against a known seed it’s still there. The honest fix is introsort’s depth check: fall back to heap sort past 2·log n levels, capping the worst case at O(n log n) by construction.

Assuming the partition preserves order. It doesn’t — equal elements jump across the pivot, which is exactly the instability. If the problem says “stable”, quicksort is the wrong answer, full stop.

Off-by-one in the final pivot swap. Swapping to store vs store ± 1 produces an array that is almost sorted and passes small tests — property testing against a reference sort (which this repo runs on every commit) is the reliable net.

Implementation notes across languages

C++’s std::sort is introsort — quicksort’s practical production form; std::nth_element is the partition alone, and knowing it exists answers the “find the k-th largest” follow-up in one line. Java uses dual-pivot quicksort for primitives but merge-derived TimSort for objects — because object sorts must be stable; that split is a great interview fact. Python’s sorted is TimSort, not quicksort at all; if an interviewer asks you to “implement Python’s sort” they’re testing whether you know that. In JavaScript, engines must be stable per spec (V8 uses TimSort), so hand-rolled quicksort is for interviews, not for shipping.