The pattern that defeats the pattern

Quicksort’s problem is that its cost depends on the pivots being near the median, and the pivots are chosen from the data, and the data may have been chosen by somebody who read the pivot rule. What randomising the pivot buys established the standard defence and its limits: a random pivot makes the bad case unlikely rather than impossible, and it destroys reproducibility, which is a real cost for a library that people debug.

There is a third option, and it is the one that has been quietly winning since 2016. Instead of avoiding bad partitions or absorbing them, notice one and break the pattern that caused it — deterministically, with a handful of swaps at fixed offsets, no randomness anywhere.

That is pattern-defeating quicksort. It is Rust’s sort_unstable, it is in Boost, and libstdc++ adopted it for std::sort in GCC 14. This essay measures the two parts of it that are about the pattern rather than about sorting.

Detecting the damage #

Introsort watches the recursion depth: if it exceeds $2\log_2 n$, quicksort has been going badly for a while and heapsort takes over. That is a cumulative signal — it takes many bad partitions to trip it, and by then the work is spent.

pdqsort watches each partition individually. After partitioning, it compares the smaller side against a fraction of the range — one eighth, in the shipped implementation. A partition that puts fewer than an eighth of the elements on one side is bad, and a bad partition is evidence that the pivot selection is being defeated by structure in the data rather than by chance.

On random input at n = 8,192 that fires 58 times in 783 partitions: 7%, which is roughly what chance produces. On reversed input it fires 363 times in 917 partitions — 40% — because the ninther pivot selection on a reversed array picks a pivot from three sampled medians of three, and the sampled positions have a fixed relationship to the array that reversal does not disturb.

Breaking it #

The response is the part that sounds too simple to work: swap a few elements at fixed offsets from the ends of the subarray, and partition again.

For a subarray running from lo to hi of length len, the shipped implementation exchanges the element at lo with the one a quarter of the way in, and the element at hi − 1 with the one a quarter of the way back from the end. On subarrays longer than thirty-two it does the same for the neighbours of those four positions.

Four swaps. No randomness. The same four swaps every time, at positions that depend only on the length.

The argument is not that this makes the data random — it plainly does not. It is that the patterns that defeat a deterministic pivot rule are patterns of the data’s own structure, and structure that survives a fixed permutation of four specific positions is a much smaller class than structure in general. An adversary who knows the shuffle can still defeat it — pdqsort makes no claim otherwise, which is why it keeps the depth limit and the heapsort fallback underneath. What the shuffle handles is the ordinary case: sorted, reverse-sorted, organ-pipe, sawtooth, and the many almost-patterns that real data contains.

The cost of the mechanism is 363 firings × 4 swaps = 1,452 swaps on reversed input, against 9,059 swaps performed by the partitions. The whole pattern-defeating apparatus costs 16% of the swaps on the input where it fires hardest, and nothing at all on sorted input, where it fires zero times.

The part that matters most, and that was nearly left out #

There is a second partition scheme in pdqsort and it is doing more work than the shuffle.

Ordinary partitioning splits into “less than the pivot” and “not less than the pivot”. Every element equal to the pivot goes to the right-hand side. On input with many duplicates that is a disaster: the equal block is carried into the recursion, one of them is chosen as the next pivot, they are split again the same way, and the algorithm spends $\Theta(k^2)$ on a block of $k$ equal elements.

The site has measured what that looks like. Median-of-three quicksort on eight distinct values in 8,192 elements takes 4,245,685 comparisons — 0.13 of $n^2/2$, comfortably quadratic, on an input containing no adversary and no unusual structure beyond repetition.

pdqsort’s answer: when the chosen pivot compares equal to the element just left of the range — which can only happen if the previous partition put a block of equals here — partition the other way instead. Split into “at most the pivot” and “greater than the pivot”, which sweeps the entire block of equals into the left part in one pass, and then recurse only on the right.

The effect is decisive:

pdqsort performs 16 partitions on that input. Introsort performs 783 on random input of the same size and considerably more here. Sixteen, because after the first few the equal blocks are swept out whole and there is nothing left to partition.

This was nearly reported as a weakness of pdqsort. The first version of lib/practice.js implemented the bad-partition detection and the shuffle and omitted the equal-element partition entirely. It sorted correctly, it passed every check, and on eight distinct values it measured a spread of 13.3 against $n \log n$ — a refused class, a catastrophic-looking result, and an essay’s worth of confident wrong conclusions about pdqsort’s handling of duplicates ready to be written.

The defect was found by measuring rather than by reading, and the direction is what gave it away: an algorithm adopted by three standard libraries in the last decade should not be five times worse than the thing it replaced on a common input. The site’s discipline says a claim is granted only if the fit holds; it took the refusal to prompt the check that found the missing code.

A library algorithm implemented with one piece missing measures as a bad algorithm, not as a broken implementation, and there is no counter that distinguishes the two. The only defence is the one used here: when a measurement disagrees with the world, suspect the measurement first.

What a good partition looks like when it goes wrong anyway #

pdqsort keeps introsort’s depth limit and heapsort fallback, and it is worth being precise about why, because the shuffle might look like a replacement for them.

The shuffle is a heuristic. It has no worst-case guarantee at all, and the reason is easy to state: it is a fixed function of the data, so there exists an input for which it makes things worse, and an adversary who has read the source can construct one. The depth limit has a guarantee — heapsort’s $O(n \log n)$, unconditionally — and it costs nothing until it fires.

A heuristic that is usually enough plus a guarantee that is always enough is the standard shape of a library algorithm, and it is the same shape as galloping’s: cheap when it does not help, decisive when it does, with something underneath that cannot fail. The depth limit that almost never fires is about the second half.

Why the equal-element case is the one that matters in practice #

It would be easy to treat duplicates as a special case, alongside sorted input and adversarial input, and to conclude that pdqsort has three defences for three rare situations. That reading is wrong about which of the three is rare.

Sorted input arrives when a program sorts something twice, or sorts data that was already ordered by the process that produced it. That is common enough to be worth handling and it is not the general case.

Adversarial input requires an adversary. Outside a security context there is not one, and inside a security context the answer is a keyed hash rather than a shuffle, as the adversary who knows the seed argues at length.

Duplicates are the general case. Any sort keyed on a field with fewer distinct values than rows has them: sorting records by department, by date, by status, by category, by priority. A million rows sorted by a boolean has two distinct values. The input this site calls fewUnique — eight distinct values in thousands of elements — is not an unusual input at all; it is closer to what most sorting in most programs actually looks like than uniformly random integers are.

So the mechanism that turns 4,245,685 comparisons into 46,004 is not a defence against a corner case. It is the difference between a usable general-purpose sort and one that quietly goes quadratic on ordinary data, and it is the reason every serious quicksort implementation since Bentley and McIlroy’s in 1993 has had some form of three-way partitioning. What pdqsort adds is doing it only where it is needed — the check costs one comparison per partition and fires on eight of sixteen partitions on duplicate-heavy input and on none at all otherwise.

The counters disagree about pdqsort too #

On random input pdqsort does 116,355 comparisons against introsort’s 134,880, and mispredicts 51,434 times against 40,025. It is 14% better on the first counter and 28% worse on the second.

That is not a defect in either algorithm. It is the difference between a Hoare partition, which runs two pointers towards each other with a data-dependent test in each loop, and a Lomuto partition, which runs one pointer with a data-dependent conditional swap. Both do about $n$ comparisons per level and their branch behaviour is completely different, and which is faster depends on a quantity — the cost of a mispredicted branch relative to a swap — that is a property of the processor rather than of the algorithm.

Which is why pdqsort’s real implementation uses neither: it uses a block partition that computes offsets into a small buffer and performs the swaps with no data-dependent branches at all. That technique is the subject of the branch the machine guesses, and it is measured there rather than here, because it makes no sense until there is a counter that can see it.

Where the shuffle fires, and where it does not #

The bad-partition detector is not a diagnostic that runs on everything. It is a claim about the data, and the pattern of where it fires is informative in its own right.

Sorted input produces no bad partitions at all. That is the ninther doing its job: sampling nine positions and taking the median of their medians gives a near-perfect pivot on sorted data, so the partitions are balanced and there is nothing to detect. The input that is quicksort’s classic disaster with a first-element pivot is quicksort’s easiest input once the pivot is chosen properly, and this site measured that in the foundation.

Reversed input produces bad partitions in 40% of them, which is the highest rate of the five and is a genuine surprise. Reversal preserves the median — the middle element of a reversed sorted array is still the median — so the ninther should pick well. What it does not preserve is the relationship between the sampled positions and the recursive subranges, and the shipped ninther samples at positions derived from the range’s length, which means after the first partition the samples fall in a systematically different place each time.

Few distinct values produces sixteen partitions in total, which is the equal-element scheme, not the shuffle. One bad partition, one break, eight blocks swept.

Reading down that table is reading the algorithm’s own model of what can go wrong. Three separate mechanisms — the ninther, the shuffle, the equal-block partition — each dominant on a different input, none of them doing anything on the inputs the others handle. That is what a library algorithm looks like from the inside, and it is why calling it “quicksort with improvements” undersells the difference: the improvements are the algorithm, and quicksort is the part that runs when none of them is needed.

The class the audit granted is really n log d #

The audit grants pdqsort a linear class on eight distinct values, and linear is a suspicious thing for a comparison sort to be. It is not linear, and the true shape is more interesting than either reading.

Sweeping an equal block out in one pass means the recursion never descends into it, so the partitions are dividing the space of distinct values rather than the space of elements. With $d$ distinct values there are at most $d$ blocks to isolate, and the measured sixteen partitions on eight values is exactly that arithmetic with a factor of two for the two sides. So the cost is

$$\Theta(n \log d)$$

— linear in the number of elements, logarithmic in the number of distinct values. The fit reports it as linear because $d$ is held at eight across the whole sweep, and a logarithm of a constant is a constant.

That is worth naming precisely, because it is the floor from a different field arriving in an algorithm. The floor when the values repeat established that sorting a multiset of $n$ elements over $d$ equally likely values requires about $n\log_2 d$ comparisons and not $\log_2 n!$ — 24,576 rather than 106,000 at these parameters. Measured, pdqsort spends 46,004, which is 1.9 times that floor; merge sort spends 92,436, which is 3.8 times it; median-of-three quicksort spends 4,245,685, which is off the scale entirely.

So the three algorithms are not three points on a spectrum of quality. They are an algorithm that reaches the floor that applies to within a factor of two, one that ignores the repetitions and pays $n\log n$ regardless, and one that is actively destroyed by them.

Two consequences worth having.

The equal-element partition is not a trick, it is the mechanism that makes the algorithm entropy-aware. Everything else in pdqsort defends against arrangements; this one responds to the value distribution, which is the quantity the floor is about. It is the only part of the algorithm that could possibly reach $n\log d$, because it is the only part that treats equal elements as finished rather than as unsorted.

And the audit’s “linear” is a statement about a held parameter. Sweeping $d$ as well as $n$ would show the logarithm, and the class the fit granted is correct over the range measured and mis-shaped as a description. That is exactly the two-parameter problem the graph field is built on, arriving in a sorting audit where nobody expected a second parameter to exist.

The audit on four more inputs #

The audit is the instrument this page is about, and an instrument run on one input is an instrument nobody has calibrated.

Both of those are orderings. The two below are not: one has almost no distinct values and one is already in order, and the second is the input a library is likeliest to be handed by accident.

And already sorted, which is the one a library is likeliest to be handed by accident and the one a run detector is supposed to make free.

What the field learned from this one #

Three things, and the third is the one worth carrying.

A response to a bad case can be cheaper than avoiding the bad case. Randomising every pivot costs randomness on every input; detecting a bad partition costs one comparison per partition and fires on 7% of them.

Determinism is a feature. pdqsort’s shuffle produces the same output for the same input every time, which means a bug reproduces, a benchmark is repeatable, and a figure on this site can quote its numbers. The randomness phase’s whole apparatus of seeds and distributions exists to recover that property after randomising it away; pdqsort simply never gives it up.

An implementation missing one branch of a policy measures as a bad algorithm. There is no gate for this, on this site or anywhere else. The four library sorts here are the first algorithms in this collection that were not fully specified by their description, and the check that caught the omission was a fit refusing a class it had no business refusing.

That last curve is the honest summary of the whole field. The gap between the textbook algorithm and the shipped one, on an input nobody would call adversarial, is a factor of ninety-two at n = 8,192 and growing. It is not a constant-factor engineering difference and it is not visible in either algorithm’s stated complexity class — both are described as quicksort, both are described as $O(n \log n)$ on average, and one of them is quadratic on data containing repeats.