Quick Sort

The 10-second versionCopy Anchor Link

Quick sort picks an element as a pivot, rearranges the array so everything smaller sits to its left and everything larger to its right, then recurses on the two sides. The rearrange is called partition, and it happens in place — no second array. The average case is O(n log n), and because it touches memory in friendly patterns it's usually the fastest general sort in practice. The danger: a badly chosen pivot degrades it to O(n²), which is why real implementations randomize the pivot and bail out to heap sort if things go sideways.

Why this existedCopy Anchor Link

Tony Hoare didn't set out to invent a sorting algorithm. In 1959, working at Moscow State University on machine translation, he needed to sort Russian words and their English equivalents so the translation dictionary could be looked up quickly. He had merge sort already — but merge sort wanted a second tape, and he didn't have one to spare. So he went looking for a sort that could run in place.

• 1959–1960 — Hoare develops the method while building his translation dictionary, first by hand, then as code.
• 1961 — He publishes it as Algorithm 64: Quicksort in Communications of the ACM, today one of the most cited algorithms ever.
• Since then — It has been the default general-purpose sort in most languages, with added safeguards, for over half a century.

Why it mattered then: it needed almost no extra memory, which was everything on the machines of the 1960s. Why it matters now: its memory access pattern plays beautifully with modern CPU caches, so it routinely outruns sorts with the same O(n log n) on paper.

Inside the inventor's headCopy Anchor Link

Hoare's starting point was the merge sort he already had: split, sort, merge. Great — except the merge step wants a second array, and memory (or tape) was the scarce resource. Could you split by value instead of by position, so that no merging is ever needed?

That's the pivot. Choose one value — the pivot. Push everything smaller to its left and everything larger to its right. After that single pass, the pivot is exactly where it belongs in the final sorted order — nothing to its left will ever move to its right, and vice versa. So you never merge; you just recurse on the two sides independently.

The first trap is the pivot choice. The lazy choice — "just take the first element" — is fine on random data and catastrophic on sorted data: on an already-sorted array, every partition peels off a single element, and you get n levels of O(n) work, which is exactly the dreaded O(n²). Watch the difference:

// Naive: the first element as pivot — O(n²) on already-sorted input.const pivotFirst = () => 0;// Improved: a random index, swapped to the front — expected O(n log n).function pivotRandom(a, lo, hi) {  const r = lo + Math.floor(Math.random() * (hi - lo + 1));  [a[lo], a[r]] = [a[r], a[lo]];  return lo;}

The third variant matters because even randomness can't stop a deterministic adversary who knows your pivot rule. Median-of-three, randomness, or both, keeps the expected depth at O(log n).

The final approachCopy Anchor Link

Partition (the Lomuto scheme)Copy Anchor Link

Keep two regions: a[lo..i] holds elements ≤ pivot, and a[i+1..j-1] holds elements > pivot. Sweep j across the array; when a[j] belongs on the left, grow the left region and swap it in. Finally, drop the pivot into the gap between the two regions and return its index.

The invariant: after processing j, every element in a[lo..i] is ≤ pivot and every element in a[i+1..j-1] is > pivot. When the sweep ends, swapping the pivot into slot i+1 puts it exactly between the two regions — every element to its left is smaller, every element to its right is larger. So the pivot is in its final position and we can recurse on each side.

A worked traceCopy Anchor Link

Partitioning [3, 7, 8, 5, 2, 1, 9, 4] with the last element (4) as the pivot:

The pivot 4 landed at index 3: [3, 2, 1] on its left, [7, 8, 9, 5] on its right. Recurse on each side. The pivot never moves again — it's already home.

It in codeCopy Anchor Link

function partition(a, lo, hi) {  const pivot = a[hi];  let i = lo - 1;  for (let j = lo; j < hi; j++)    if (a[j] <= pivot) { i++; [a[i], a[j]] = [a[j], a[i]]; }  [a[i + 1], a[hi]] = [a[hi], a[i + 1]];  return i + 1;}function quickSort(a, lo = 0, hi = a.length - 1) {  if (lo >= hi) return a;            // 0 or 1 element: sorted  const p = partition(a, lo, hi);  quickSort(a, lo, p - 1);  quickSort(a, p + 1, hi);  return a;}

ComplexityCopy Anchor Link

The O(n²) worst case is real: feed it sorted input with a first-element pivot and it peels off one element per level. Random or median-of-three pivots make that astronomically unlikely on real data — but "unlikely" isn't a guarantee, which is why production sorts don't stop here.

The fix: introsortCopy Anchor Link

Modern libraries refuse to gamble. Introsort runs quick sort, tracks the recursion depth, and if it exceeds 2·log n it switches to heap sort — guaranteed O(n log n) — and finishes small ranges with insertion sort. You get quick sort's speed in the common case and a hard ceiling in the worst case. That's what std::sort does.

Where you meet it todayCopy Anchor Link

• C++ std::sort. Introsort: quick sort, with heap sort and insertion sort as the safety nets. The default in one of the most-used languages on the planet.
• Go's sort. A pattern-defeating quick sort (pdqsort) with the same guarantees.
• Quickselect. Drop one side of every recursion and you get the k-th smallest element in expected O(n) — the algorithm behind nth_element (C++) and select_nth_unstable (Rust), used for medians and top-k.
• Interviews. Partitioning is the trick behind many "rearrange in place" problems, like moving all evens before all odds.

function quickselect(a, lo, hi, k) {  if (lo === hi) return a[lo];  const p = partition(a, lo, hi);  if (k === p) return a[p];  return k < p ? quickselect(a, lo, p - 1, k)               : quickselect(a, p + 1, hi, k);}

RecapCopy Anchor Link

• Quick sort: pick a pivot, partition in place, recurse on both sides. The pivot lands in its final position every time.
• Average O(n log n) with excellent cache behaviour; worst case O(n²) on bad pivots.
• Pivot choice is the whole game — random or median-of-three keeps the expected depth at O(log n).
• Real libraries use introsort: quick sort, with heap sort as the guaranteed fallback and insertion sort to finish small runs.
• Quickselect (recurse one side) finds the k-th element in expected O(n).

Next up: Heap Sort — the guarantee that introsort falls back on when quick sort's luck runs out.