What randomising the pivot buys

Quicksort’s reputation rests on a claim with a qualifier, and the qualifier is doing all the work.

Quicksort is $\Theta(n \log n)$ on average, and $\Theta(n^2)$ in the worst case. Whether that matters depends entirely on whether the worst case is something that happens in practice, and for the textbook version of the algorithm it happens on the most ordinary input imaginable.

At $n = 512$, taking the first element as the pivot:

130,816 is $\frac{512 \times 511}{2}$ — every possible pair compared, which is the absolute maximum. The algorithm has degenerated into something worse than insertion sort, on data that was already in order.

Why sorted input is the worst case #

The partition step picks a pivot and splits the array into elements below it and elements above. The recursion is efficient when those two parts are about equal and useless when one of them is empty.

If the pivot is the first element of an already sorted array, it is the smallest element. Nothing is below it. The partition produces one empty part and one part of size $n-1$, and the recursion descends $n$ levels doing $n$, $n-1$, $n-2$, … comparisons. That is the quadratic sum.

The same happens on reversed input, where the first element is the largest. And on nearly sorted input the effect is nearly as bad: 120,301 comparisons at $n = 512$, which is 92% of the maximum.

So the rule “take the first element” has a bad case, and the bad case is sorted or nearly sorted data. That is not an exotic input — it is what real data very often looks like, for exactly the same reasons that make sorted insertion order the default for a binary search tree.

What randomising changes #

Choosing the pivot uniformly at random from the current range changes the guarantee in a way that is easy to state and easy to under-appreciate.

Before: quicksort is fast if the input is randomly ordered. This is a claim about the data. It may not be checkable, it may be false, and an adversary who can influence the input can make it false deliberately.

After: quicksort is fast unless the coin flips go badly. This is a claim about the algorithm’s own randomness. It holds on every input — sorted, reversed, adversarial, anything — because the input no longer selects which case arises.

The measured consequence at $n = 512$: the randomised version costs 4,921 comparisons on random input and 5,490 on sorted input. The two are within 12% of each other. Sorted input is no longer special.

That is the whole of what randomisation buys, and it is worth being precise that it is not “the bad case cannot happen”. It can. A random pivot can land at the minimum every single time, and the probability of that is $1/n!$ — astronomically small and not zero. What has changed is that nothing about the input affects that probability.

Average case against expected case #

The distinction the previous section is making has a name, and mixing the two up is the most common error in this area.

Average case is averaged over an assumed distribution of inputs. First-element quicksort is average-case $\Theta(n \log n)$ given uniformly random input, and the guarantee evaporates the moment the data is not uniformly random.

Expected case is averaged over the algorithm’s own randomness, and it holds for every input. Randomised quicksort is expected $\Theta(n \log n)$ on all inputs, full stop.

The second is a much stronger guarantee and it is bought at a price: the algorithm needs a source of randomness, its behaviour is no longer reproducible run to run, and debugging becomes harder because a failure may not repeat. Those are real costs, and they are why some systems seed the randomness deterministically — recovering reproducibility at the price of becoming, once again, vulnerable to an adversary who knows the seed.

The three meanings of “average” — average case, expected case, and amortised — are three different guarantees written with the same word, and this is the pair that gets confused most often.

The adversarial case is not hypothetical #

It would be easy to treat “an adversary chooses the input” as a theoretical concern. It is not.

Any service that sorts data supplied by its users is in exactly this position. If the sort uses a deterministic pivot rule, a user who knows the implementation can construct an input that triggers the quadratic case, and a request that should have taken a millisecond takes a minute. Repeat it a few times and the service is down.

This is a real and named attack — algorithmic complexity denial of service — and it has been used against hash tables, regular expression engines, and sorting routines in production systems. The defence in every case is the same shape: introduce randomness the attacker cannot predict, so that the input’s structure stops determining the cost.

Which is why the standard advice is not “use median-of-three, it usually works”. It is: randomise, or use an algorithm with a worst-case guarantee.

What median-of-three does and does not fix #

The cheaper alternative to randomisation is to look at the first, middle and last elements and use their median as the pivot.

It works, in the sense that it removes the specific bad cases. On sorted input the middle element is the median of the whole array, so the partition is perfect and median-of-three costs 4,363 comparisons at $n = 512$ — better than its 5,049 on random input.

It does not work, in the sense that it is still deterministic. There exists an input that makes median-of-three quadratic; it is just harder to construct. Sequences designed to defeat it are well known and can be generated by an adversary who knows the implementation. The rule raises the bar and does not change its kind.

The honest summary: median-of-three is an excellent defence against accidentally sorted data, which is the overwhelmingly common case, and no defence at all against a deliberate attack. For input produced in-house, use it. For input arriving from the internet, randomise.

What randomisation costs #

Nothing is free, and the costs of a randomised pivot are worth listing because they are the reason median-of-three is still widely used.

Randomness has a price. Generating a random number per partition is not expensive but it is not nothing, and on small subarrays — where a production sort spends a surprising amount of its time — the cost is a measurable fraction of the partition itself. Some implementations randomise only at the top few levels for this reason.

Reproducibility is lost. A bug that appears once in a thousand runs and cannot be reproduced is much harder to fix than a deterministic one. Implementations that care about this seed from a fixed value, which restores reproducibility and reopens the adversarial hole — an attacker who knows the seed knows the pivot sequence.

The comparison count gets slightly worse. Measured on random input at $n = 512$, the randomised rule costs 4,921 comparisons against the first-element rule’s 4,887. The difference is under 1% and it is real: a random pivot is on average a slightly worse pivot than an arbitrary one on already-random data, because neither has any information and randomising adds variance without adding information.

That last point is the honest summary of the whole trade. On genuinely random input, randomising the pivot makes quicksort microscopically worse. Everything it buys is on the inputs that are not random, and the reason to pay is that which kind of input is arriving is usually unknowable.

The input where no pivot rule helps #

There is a case that defeats all three rules equally, and it is not adversarial at all.

An array with few distinct values — sorting a million records by a status field with eight possible states, say. At $n = 512$ with eight distinct values:

All three degrade by roughly a factor of four, and the site’s fitting machinery classifies all three as quadratic on this input.

The reason is that the problem is not in the choice of pivot. It is that a two-way partition places every element equal to the pivot on one side, so when many elements equal the pivot, the split is unbalanced no matter how well the pivot was chosen. Randomising the choice cannot help, because there is no choice that helps — and the site’s fit refuses to grant any of these three a class on this input, which is the machinery noticing the same thing.

The fix is a three-way partition: separate the array into less-than, equal-to and greater-than, and recurse on the two outer parts only. Every element equal to the pivot is finished immediately. This is what production quicksorts do, and it costs a few comparisons on ordinary input to buy safety on this one — a trade that is invisible to anyone who only ever benchmarks random arrays.

The same defence, in three other places #

Randomisation as a defence against structured input is a pattern rather than a quicksort trick, and recognising it makes several unrelated-looking designs into one idea.

Hash tables. A fixed, public hash function lets an attacker compute colliding keys and turn a table into a linked list. Seeding the hash per process, from a source the attacker cannot see, moves the guarantee from an assumption about the keys to the algorithm’s own randomness — exactly the same upgrade that randomising a pivot makes.

Skip lists and treaps. Both replace a balanced tree’s rebalancing rules with a coin flip, and both get expected logarithmic height on any insertion sequence. An unbalanced binary search tree is the version without the coin, and sorted input destroys it.

Randomised load balancing. The “power of two choices” result — pick two servers at random and send the request to the less loaded — is the same shape at a different scale: randomness removes the input’s ability to concentrate work.

In each case the deterministic version is faster on typical input by a small margin and has a catastrophic case that the input can select. The randomised version gives up the margin and takes the selection away.

The randomness has to be unpredictable, not merely random-looking #

The security half of the argument has a requirement the complexity half does not, and it is easy to satisfy the second while believing the first has been satisfied too.

Every measurement on this site uses a seeded xorshift32 generator with the seed printed in the caption. That is a deliberate choice and it is what makes the numbers reproducible: a figure whose counts change on every build is a figure whose caption cannot quote them. For the distributional claims in this essay — that the expected cost is the same on every input, that the spread is stable — a seeded generator is exactly right, because the claim is about the distribution and the distribution does not care whether anybody can predict the draw.

As a defence against a chosen input it is worth nothing at all. An attacker who knows the implementation knows the generator; xorshift32 has 32 bits of state and its output is its state, so a single observed pivot choice reveals every subsequent one. Seeding it from the clock is not much better, since the clock is guessable to within a small range and the range can be searched offline. The killer input can then be constructed exactly as it could against a deterministic rule, and the expected-case theorem is untouched by any of this — it was always conditioned on the pivots being drawn independently of the input, and an attacker who can predict the pivots has made the input depend on them.

The same distinction is why hash tables in language runtimes moved to keyed hashes such as SipHash rather than to merely better-mixing ones. Mixing defeats accidental clustering; only an unpredictable key defeats a chosen one. The probe formula essay shows the accidental version — a stride that shares a factor with the capacity — and the fix for that is a better hash. The fix for the deliberate version is a secret.

So “randomise the pivot” is two recommendations wearing one name. Against unlucky data, any decent generator works and reproducibility is a virtue. Against chosen data, the generator must be unpredictable to the party choosing, and a reproducible one is precisely the wrong thing.

Where randomisation is not the answer #

Two cases, and both are worth knowing so the pattern is not over-applied.

When a worst-case guarantee is required. Randomisation gives an expected bound; a hard real-time system needs a bound that holds always. Heapsort’s $\Theta(n \log n)$ worst case with no bad inputs is worth its factor of two in the constant precisely here, and introsort — quicksort that switches to heapsort when the recursion gets too deep — is the standard way to get both.

When the problem is in the data rather than the order. Few distinct values, covered above. No pivot rule of any kind helps, because there is no pivot that produces a balanced two-way split.

The fourth row, which fills every column #

The table in the next section has three rows and each of them leaves at least one column empty. There is a fourth defence that fills all three, and it is the one every standard library actually ships.

Bound the recursion depth and fall back. Introsort counts levels, and when the depth exceeds about twice the logarithm of the input it abandons quicksort for heapsort — which is $\Theta(n\log n)$ on every input, with no pivot to choose and no bad case at all.

That covers all three columns at once, and it covers them for one reason rather than three. Every failure in this essay shows up as an unbalanced recursion: sorted input with a first-element pivot descends $n$ levels; an adversarial input against median-of-three descends $n$ levels; few distinct values descends deeply because the equal block keeps landing on one side. The depth counter does not care which of the three caused it. It sees the symptom that all of them share.

That is worth noticing as a design principle rather than as a fact about introsort. A defence aimed at a mechanism protects against one cause; a defence aimed at a symptom protects against all the causes that share it, including the ones nobody has thought of. The pivot rules on the table are mechanism defences and each has a gap; the depth limit is a symptom defence and has none.

Two honest qualifications, because the row is not free.

It does not make quicksort good on those inputs, it makes it not terrible. The fallback is heapsort, whose comparison constant is about twice merge sort’s and whose memory behaviour is worse. A run that falls back has stopped being fast and has stopped being catastrophic, which is the whole product.

And the threshold is a real parameter with a real trade. A limit that fires too readily makes ordinary sorts pay heapsort’s constant; one that fires too late lets the quadratic case run for a while first. The measured behaviour is that the depth factor barely matters on random input and matters a great deal on duplicates — which is the same asymmetry the rest of this essay is about, arriving as the setting of a constant rather than as the choice of a rule.

So the honest summary of the four rows is that three of them make the bad case rarer and the fourth makes it bounded, and every production sort takes the fourth as well as one of the first three.

The three rules at three sizes #

The three rules are what the page is about, so the comparison is drawn again at two more sizes and once with the middle rule left out.

Both of those hold the seed count fixed, and the width of a measured distribution depends on how many draws went into it.

And the last plate drops the middle rule, because the argument the page is making is between two things and the third is what a reader keeps reaching for instead.

What the numbers say in total #

Three defences, three different things bought:

The columns are independent, which is why real implementations use two or three of these together rather than picking one — and why a single number cannot summarise an algorithm. And the reason to lay it out this way is that “quicksort is $\Theta(n \log n)$ on average” collapses all three columns into a claim with no columns at all.