Quick Sort
Pick a pivot, split around it, recurse — the cache-friendly in-place sort that most systems code is built on.
Hands on Interactive visualization
Implementation Code
export function quickSort(
a: number[],
lo = 0,
hi = a.length - 1,
): number[] {
if (lo >= hi) return a;
// Lomuto partition around a[hi].
// Production code should randomize the pivot to avoid O(n^2) input.
const pivot = a[hi];
let i = lo; // boundary: a[lo..i) holds elements < pivot
for (let j = lo; j < hi; j++) {
if (a[j] < pivot) {
[a[i], a[j]] = [a[j], a[i]];
i++;
}
}
[a[i], a[hi]] = [a[hi], a[i]]; // pivot lands in its final slot
quickSort(a, lo, i - 1);
quickSort(a, i + 1, hi);
return a;
}Big-O Complexity
O(n²) triggers on adversarial pivots (e.g. sorted input with first/last-element pivots); randomization or median-of-three makes it vanishingly rare. Space is recursion stack.
In production When to use
Quicksort descendants are the default unstable sort in systems languages: Go's slices.Sort uses pdqsort (since Go 1.19), Rust's sort_unstable is pdqsort-based, C++'s std::sort is introsort (quicksort + heap sort fallback), and Java sorts primitives with dual-pivot quicksort.
In-place partitioning with only O(log n) stack makes it the go-to for sorting large arrays without doubling memory, unlike merge sort's O(n) buffer.
Quickselect — quicksort recursing into one side only — finds the k-th smallest element in expected O(n): medians, percentiles, top-k without a full sort.
In-memory sort steps in query executors commonly use quicksort variants when stability is not required and the working set fits in RAM.
Sorting large arrays of primitives where stability is meaningless (identical floats are indistinguishable) plays to quicksort's strengths: no allocation, great cache locality.
Trade-offs Strengths & weaknesses
- Fastest general-purpose comparison sort in practice: tight inner loop, sequential scans, excellent cache locality.
- In-place — only O(log n) stack, no O(n) buffer.
- Partitioning is a useful primitive on its own (quickselect, Dutch national flag, top-k).
- Average O(n log n) with constants that beat merge sort on arrays.
- Well-studied hardening options: random pivots, median-of-three, introsort depth cutoff.
- O(n²) worst case — must be actively defended against in adversarial settings.
- Not stable: equal keys can be reordered by long-range swaps.
- Naive Lomuto partitioning degrades to O(n²) on arrays of many equal elements.
- Recursion depth can blow the stack without tail-call elimination on the larger side.
- Performance depends on pivot quality — a bad strategy silently costs orders of magnitude.
Intuition Mental model
Lining up by height against a reference person
Pick one person (the pivot) and ask everyone to stand left if shorter, right if taller. That person is now permanently placed; repeat within each side.
- Choose a reference person from the group — ideally at random, so no arrangement of the group can consistently trick you.
- Everyone shorter moves to the left of them, everyone taller to the right — one linear pass.
- The reference person is now in their exact final spot and never moves again.
- Repeat the game independently inside the left group and the right group.
- If you keep unluckily picking the shortest person, one side holds everyone — that lopsidedness is the O(n²) worst case.
Prep Interview questions
Why is quicksort usually faster than merge sort despite the same average complexity?
What input triggers quicksort's O(n²) worst case and how do production sorts prevent it?
Lomuto vs Hoare partitioning — trade-offs?
How do you sort an array with millions of duplicate keys efficiently?
How do you cap quicksort's stack usage at O(log n) even in the worst case?
Watch out Common bugs
With all-equal input, Lomuto with < pivot puts everything on one side; if the recursive bounds are off by one, the subproblem never shrinks. Always exclude the pivot's final index from both recursive calls.
Choosing a pivot value by index and then swapping during partitioning means the index no longer points at the pivot. Save the value, or move the pivot to a known slot (end) first.
In 32-bit integer languages, lo + hi overflows on large arrays when picking a middle pivot. Use lo + (hi - lo) / 2.
Hoare's returned index is a split point, not the pivot's final position. Treating it like Lomuto's return value (excluding index p from both sides) drops elements or loops forever.
One screen Cheat sheet
Partition around a pivot so smaller is left, larger is right; the pivot lands in its final slot; recurse both sides.
- Fastest comparison sort in practice — cache locality and in-place swaps.
- Worst case O(n²) needs a defense: random pivot, median-of-three, or introsort fallback.
- Not stable; use merge/TimSort when equal-key order matters.
- Many duplicates? Use three-way (fat) partitioning.
- Recurse into the smaller side, loop on the larger, to bound stack at O(log n).
- Partitioning alone gives you quickselect for expected-O(n) top-k.