Shuffling before sorting

Why does deliberately disordering data first make a sorting method dependable?

Here is an instruction that sounds like a joke: before sorting your data, shuffle it into random order. You are about to impose order, and the first thing you do is destroy what order there was.

Stranger still, this is not a heuristic that usually helps. It converts a method with a genuinely terrible worst case into one that is dependable on every input anybody can hand you. How can adding randomness make behaviour more predictable rather than less?

Look first at what quicksort does. Pick one element as the pivot, partition the rest into those below it and those above, then sort the two sides the same way. Ask the obvious question: what makes a partition good?

Balance. If the pivot lands near the middle, the two sides are each about half the size, and the halvings stack up so that the recursion is only about log2 n deep, with each level costing n work — so n log n. If the pivot lands at an extreme, one side gets everything and the other gets nothing: the depth becomes n, and the total becomes n squared.

Now the classic embarrassment. Take the simplest pivot rule — always use the first element — and feed it an already sorted array. Every pivot is the minimum of what remains, every partition is maximally unbalanced, and sorting a sorted array takes quadratic time. The input most likely to arrive in practice is the input that breaks it worst.

So patch the rule. Use the middle element; use the median of the first, middle and last. Better in practice. But ask the sharper question: has the class of bad inputs disappeared, or merely moved? Any deterministic pivot rule is a fixed function of the array's contents, so somebody who reads your code can compute which arrangement makes every pivot extreme. Douglas McIlroy showed this concretely in 1999, building an adversarial comparison function that drives median-of-three quicksort to quadratic time while answering each comparison consistently — deciding the order as the algorithm asks, rather than fixing it in advance. Determinism means a bad input exists; it does not vanish, it just gets harder to name.

Here is the move. Choose the pivot by a coin flip — a uniformly random index — or, equivalently, shuffle once at the start and then always take the first element. What has changed?

Not the worst case. It is still quadratic; a run of astonishingly unlucky flips still produces the same collapse. What changed is where the uncertainty lives. Before, the cost depended on the input, which your adversary controls. Now it depends on your coins, which the adversary does not see and cannot influence. There is no longer any such thing as a bad input — only a bad run, and a bad run is bad by chance rather than by design.

And chance is quantifiable. Take a random pivot and its rank is uniform, so the expected number of comparisons works out to about 2n ln n — roughly 1.39 times n log2 n, only about forty per cent above the information-theoretic floor. More useful than the expectation is the concentration: the probability of taking more than a small constant multiple of n log n comparisons falls off polynomially in n, so at any realistic size the quadratic case is not something you plan around. Sorting a million elements badly would require a coincidence of a sort no one has observed.

Is expectation enough for you, though? Sometimes not. If a hard deadline matters, the honest engineering answer is not to argue about probabilities but to remove the tail: introsort, introduced by David Musser in 1997, runs randomized quicksort but counts recursion depth and switches to heapsort when the depth exceeds a multiple of log n. Quicksort's speed on the ordinary case, heapsort's guaranteed n log n on the pathological one. This is what the C++ standard library's sort does, and it is why the worst case there is a bound rather than a hope.

Two corrections, both common.

The first is the belief that randomizing makes quicksort's worst case n log n. It does not. The worst case stays quadratic; the expected case is n log n for every input, which is a different and, for most purposes, better guarantee. Compare the two statements carefully: "fast on typical inputs" is an assumption about the world that may be false, while "fast in expectation on any input" is a property of the algorithm that no data can violate.

The second is subtler: randomization did not reduce the total amount of badness in the system, it relocated it. Deterministic quicksort has rare bad inputs; randomized quicksort has rare bad coin sequences. What makes the trade worthwhile is not that the second is rarer but that it is independent of anything an adversary can arrange, and that repeating a slow run on the same data is very unlikely to be slow again. Both matter — a source of randomness the attacker can predict, as with a seeded generator whose seed is guessable, gives the guarantee straight back to them.

• Yao's minimax principle, which formalises the relationship between randomized algorithms and worst-case inputs.
• The Fisher-Yates shuffle, and why the naive shuffle that looks equivalent produces a biased permutation.
• Timsort and other adaptive sorts, which take the opposite view — exploiting the existing order rather than destroying it.

Every term the collection defines is gathered in the glossary.