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.

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.

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.