Quicksort — every question, written out
Partition around a pivot that lands exactly where it belongs, then recurse on each side. The fastest comparison sort in practice. In place and cache-friendly.
Read the quicksort explanation and watch it run
Why is quicksort O(n log n) on average? Not what — why.
Complexity derivation
Each level partitions every element once, and balanced pivots give about log n levels
A partition pass touches every element in its range, so one whole level of the recursion costs O(n) no matter how the ranges are divided. Balanced pivots halve the ranges, giving log n levels, and n per level times log n levels is the product. Both halves of that reasoning are load-bearing — the levels alone are not the answer.
See it run — The first partition covers the whole array: every element inspected once, at one level.
What input shape drives quicksort to O(n²), and what exactly goes wrong?
Complexity derivation
Any input where the chosen pivot is repeatedly an extreme value, so each partition peels off one element
The cost is set by how evenly the pivot divides its range. An extreme pivot leaves n−1 elements on one side, so the depth becomes n instead of log n while each level still costs O(n). Which inputs produce extreme pivots depends entirely on the pivot rule, which is why "sorted input is quadratic" is only true for naive first-element pivots.
Given that, what does median-of-three actually buy you — and what does it not protect against?
Trade-off & selection
It defeats the sorted and reversed adversaries cheaply, but not adversarial or heavily duplicated input
Sampling three elements costs O(1) and kills the two adversaries that occur constantly in practice — already-sorted and reversed data. It is a heuristic, not a bound: randomised pivots defend against adversaries in expectation, and duplicate-heavy input needs a three-way partition instead. In Prism’s trace, sorted input finishes at depth 4 on 16 elements, which is what "defended" looks like.
See it run — Sorted input, and the first pivot still lands mid-array at index 7 — a balanced split.
What happens to this quicksort on an array where every element is equal?
Edge case reasoning
Lomuto partitioning sends every element to one side, so it locks one element per partition and goes quadratic
With `a[i] < pivot` as the test, elements equal to the pivot never move left, so every element lands on the same side and the split is n−1 to 0. The trace shows it plainly: 16 equal keys take 521 steps against 283 for random input, locking a[0], then a[1], then a[2] in turn. The fix is three-way partitioning, which groups equal keys with the pivot and makes this the best case.
See it run — The first partition locks a[0] only — one element for a whole linear pass.
What is always true at the top of the partition loop, just before `a[i]` is examined?
Invariant identification
Everything left of `store` is smaller than the pivot, and everything from `store` to `i` is at least the pivot
The two regions are what the loop maintains: a prefix of confirmed-smaller elements ending at `store`, and a middle band of confirmed-not-smaller elements running up to `i`. Everything from `i` to the pivot is simply unexamined. When the loop ends, swapping the pivot into `store` puts it exactly where those two regions meet — which is its final position.
See it run — The invariants panel states both halves of this while the store pointer advances.
Why is quicksort guaranteed to terminate, even in its worst case?
Invariant identification
Every partition places at least one element — the pivot — permanently, and never revisits it
The pivot lands in its final sorted position and is excluded from both recursive calls, so each level of the recursion permanently settles at least one element. That is enough for termination regardless of how lopsided the splits are. In the drawing it is the settled strip filling in, one locked position at a time.
After the first partition of a 16-element array completes, how many positions are permanently settled — and which?
Trace prediction
Exactly one: the pivot, at wherever the store index finished
One partition makes exactly one permanent placement. Everything else has merely been sorted into "smaller than the pivot" and "at least the pivot", which is a weaker claim than being in final position. Watching the settled strip fill one cell per partition is the clearest picture of that distinction.
See it run — The first locked cell appears in the strip under the baseline — one, not many.
A Lomuto partition is written `for (let i = lo; i <= hi; i++)` with the pivot parked at `hi`. What breaks?
Code diagnosis
The pivot compares against itself and can be swapped away from `hi`, corrupting the final placement
The pivot is deliberately held at `hi` and excluded from the scan; the loop must stop at `hi - 1`. Including it lets the pivot be compared with itself and swapped into the smaller region, after which the final `swap(store, hi)` moves the wrong element into the "final" position. The result is a sort that silently returns wrong answers on some inputs rather than crashing.
Both quicksort and merge sort are O(n log n) on average. When does the difference actually matter?
Comparison
When memory is tight or worst-case latency must be bounded — quicksort sorts in place, merge sort guarantees the bound
Quicksort uses O(log n) stack and no auxiliary array, so it wins where memory is scarce and average speed is what matters. Merge sort pays O(n) extra space and buys a hard O(n log n) ceiling plus stability, which is why it backs library sorts on linked lists, external data, and multi-key records. The choice is memory and predictability, not raw speed.
Now suppose the data does not fit in memory. Which of the two adapts, and how?
Trade-off & selection
Merge sort — sort chunks that fit, write them out, then merge the sorted runs in a streaming pass
Merge sort only ever reads its inputs front to back, which is the access pattern external storage is built for. The standard shape is: sort memory-sized chunks, spill them as sorted runs, then k-way merge those runs with one buffered reader each. Quicksort’s in-place advantage evaporates because partitioning demands random access over the entire range.
Why do production implementations usually prefer Hoare partitioning over Lomuto?
Comparison
Hoare does about three times fewer swaps on average and copes far better with duplicate keys
Hoare’s two pointers converge from both ends and swap only when a genuinely misplaced pair is found, which is roughly a third of Lomuto’s swap count. It also splits arrays of equal keys near the middle instead of peeling one element per pass. The cost is a subtler contract: the returned index is a split point, not the pivot’s final home, so the recursion must be written accordingly.
Why do real implementations switch to insertion sort for small subarrays?
Trade-off & selection
Below a threshold of roughly 10–30 elements, insertion sort’s tiny constant beats the recursion and pivot overhead
Asymptotics describe the trend, not the crossover point. On a handful of elements the cost of choosing a pivot, calling a function and partitioning exceeds simply shifting a few values into place, and insertion sort also runs almost linearly on the nearly-ordered ranges quicksort leaves behind. The threshold is tuned empirically per implementation, which is why it varies between libraries.
You sort records by name, then by department with quicksort. Why might the names come out shuffled?
Edge case reasoning
Quicksort is unstable: partitioning swaps distant elements, so equal departments lose their previous name order
Stability means equal keys keep their relative order, which is what makes sort-by-name-then-by-department work. Quicksort swaps elements across arbitrary distances during partitioning, so two records in the same department can trade places for reasons unrelated to their names. Use a stable sort for the later passes, or sort once on a composite key.
Describe quicksort to someone who does not code. Say it out loud before revealing.
Explain it plainly
Imagine sorting a pile of exam papers by score. Pick one paper — say it scored 60 — and hold it up. Go through the rest of the pile once, dropping every paper below 60 on your left and every paper at or above 60 on your right. Now put the 60 between the two piles: it is in exactly the right place forever, because everything before it is lower and everything after is higher, and you never touch it again. You are left with two smaller piles, and you do the same trick on each. Keep going and the piles get small enough to be trivially in order. The one catch: if you keep picking the highest or lowest paper as your marker, the piles do not really split — you peel one sheet off at a time and it takes far longer.
The test is whether the listener could carry out the procedure themselves. A strong answer names the pivot, the split, and the recursion without using those words, and lands the key insight that the pivot is finished the moment the split is done.