Quicksort

## What actually costs anything Quicksort sorts a range by choosing one element as the **pivot**, rearranging the range so that everything not greater than the pivot sits to its left and everything greater sits to its right (**partitioning**), then recursing on the two sides. Partitioning a range of size `m` touches each element a constant number of times, so it costs `O(m)`. That single fact drives the whole analysis. Look at the recursion as a tree of levels. Every level partitions a set of disjoint subranges whose sizes add up to at most `n`, so **each level costs O(n)**. The total cost is therefore `O(n) x (number of levels)`, and the number of levels is decided entirely by how evenly pivots split their ranges. ## The two extremes **Balanced splits.** If each pivot lands near the middle, a range of size `m` becomes two of size about `m/2`. Halving from `n` down to 1 takes `log2 n` steps, so there are about `log2 n` levels, each `O(n)`: total `O(n log n)`. **Degenerate splits.** If each pivot is the smallest (or largest) element of its range, one side gets `n-1` elements and the other gets nothing. The recursion becomes a chain of length `n`, and the work per level shrinks only by one element each time: ``` n + (n-1) + (n-2) + ... + 1 = n(n+1)/2 = O(n^2) ``` So the quadratic case is not caused by partitioning suddenly becoming slow. Partitioning stays linear; there are simply `n` levels of it instead of `log n`. ## Which inputs trigger it The trigger is a **pivot rule that is blind to the data plus input that is arranged against that rule**: - **Fixed-position pivot on ordered input.** Take the first element as pivot on ascending input and it is the minimum of every subrange; take the last element on ascending input and it is the maximum of every subrange. Either way you get the degenerate chain. Reverse-sorted input does the same. This is the case that bites in production, because sorted input is not exotic: an upstream stage adds an ordering step, a batch arrives already grouped by key, a file was written in key order, and a sort that was fine for a year goes quadratic overnight. - **Middle-position pivot** is not safe either — it is merely harder to hit by accident. Any deterministic pivot rule has an input class that defeats it, and someone who controls the input can construct one. - **Massive duplication** can also produce maximally unbalanced splits, depending on how the partition scheme treats keys equal to the pivot; that is a separate failure with a separate fix. ## The direction of each claim Three points get stated backwards constantly, and interviewers listen for them: 1. **`O(n^2)` is an upper bound, not a prediction.** It says quicksort never does asymptotically worse; it does not say real input makes it do that. On a uniformly random permutation the expected comparison count is about `2n ln n ~= 1.39 n log2 n` — a small constant above the balanced ideal. 2. **"Balanced" does not mean "exactly half".** A pivot that always splits 9:1 gives depth `log(n) / log(10/9)`, still logarithmic; the constant factor grows, the asymptotic class does not. Quicksort only breaks when the small side is a *constant number of elements* rather than a constant *fraction*. 3. **Average case is not the same as worst case.** The average assumes an input distribution; the worst case makes no assumption and is what an adversary, or an unlucky upstream change, actually hands you. ## What helps, and how far The standard first-line hardening is **median-of-three**: look at the first, middle and last elements of the range and pivot on their median. On already-sorted and reverse-sorted input this picks the true middle element, so the two shapes that cause almost all accidental blowups disappear. It is cheap — three comparisons per call — and it also gives insertion-sort-friendly behaviour on nearly-ordered data. But be precise about what it buys. Median-of-three **does not change the worst-case bound**. It is still a deterministic rule reading three fixed positions, so an input can be constructed that feeds it a near-extreme pivot every time, and the result is still `O(n^2)`. The honest answer to "is median-of-three enough?" is: it removes the accidental worst cases you will hit from ordinary data, not the theoretical one, and not one chosen by someone who knows your pivot rule. The answer an interviewer wants at this level is the mechanism, not a slogan: cost equals levels times linear work per level, the pivot decides the number of levels, and ordered input against a fixed-position pivot is the classic way to get `n` levels instead of `log n`.