A worst case ten positions wide

The worst case found by climbing ran a search that swaps two positions at a time towards a more expensive input, and it could not find first-element quicksort’s worst case at sixty-four elements although that worst case is sorted input, the best-known bad input in sorting. The search stopped on an ordering from which no swap helped, at half the worst count. That suggested something about sorted input itself — that it sits on a narrow peak, and that orderings a few swaps from it are far cheaper than it is.

A worst case is always reported as one input and one number. The number says how bad the worst input is. It says nothing about how many inputs are that bad, or about what the inputs near it cost, and those are what decide whether a worst case is a hazard in practice. Real data is rarely a random permutation and rarely an exact worst case either. It is sorted by something and then appended to, reversed except for a few late arrivals, or the output of a previous sort with a handful of updates. If a worst case survives a little disorder, data like that will find it. If a little disorder destroys it, data like that is safe, and the worst case is a warning about a single, exact, unusual input.

This page measures that property directly, first exactly on eight elements and then at the sizes enumeration cannot reach.

How many inputs are the worst #

The simplest measure of how wide a worst case is is how many inputs share it. At eight elements every ordering can be counted.

The spread is a factor of eighty, and it follows the structure of the algorithms rather than their names.

First-element quicksort’s 128 is $2^7$. Its count reaches 28 only when every pivot is the smallest or the largest element of the range it partitions, so that every partition peels off one element. Seven partitions of ranges longer than one, two choices each. Insertion sort’s 128 has the same form for a different reason. Inserting the element at position $i$ costs at most $i$ comparisons, and it costs exactly $i$ when that element is the smallest or the second smallest of those before it — two choices at each of seven insertions. Sorted input for the one and reversed input for the other are single members of a set of 128, and the other 127 are orderings no benchmark generator would name.

Merge sort’s worst case is a quarter of all inputs. Its count reaches 17 whenever every merge runs to its last element, and a merge runs to its last element exactly when the two largest elements it holds come from different halves. For the top merge of eight that happens with probability 4/7, and for each of the two merges of four below it with probability 2/3; the orderings inside each half are independent of which elements the half holds, so the three multiply, and $\tfrac{4}{7}\cdot\tfrac{2}{3}\cdot\tfrac{2}{3} = \tfrac{16}{63}$ of 40,320 is exactly 10,240. A count over every input found merge sort’s worst case to be an ordering no benchmark produced; the reason no benchmark needs to produce it is on this plate, because a quarter of random orderings reach it and its margin over the mean, 17 against 15.73, is barely more than a comparison.

Median-of-three quicksort’s 5,760 is exactly one in seven. Heapsort’s 432 is about one in a hundred, and the only width among the five with no short explanation.

One swap away, and seven #

Size is half the picture. The other half is the neighbourhood: how quickly the count falls as an ordering moves away from the worst. At eight elements the distance can be measured exactly, as the fewest swaps that turn one ordering into another, and every ordering sits at a distance between zero and seven from each sort’s worst.

Taking the gap between the mean and the worst as the thing being lost, one swap costs heapsort 31% of it, insertion sort 37%, first-element quicksort 48%, median-of-three quicksort 56% and merge sort 59%. In comparisons rather than shares, first-element quicksort’s fall is by far the largest — 5.36 comparisons in a single swap, against 3.25 for insertion sort and under two for the other three — because its gap is the largest to begin with.

The farthest orderings, seven swaps from the worst, cost no more than the sort’s average and usually less. Being as far as possible from one ordering is itself a constraint, and for all five sorts it pushes the count to the cheap side.

Eight elements are too few to separate a narrow peak from a broad one convincingly, because every ordering is within seven swaps of every other. What the plate establishes exactly is that no worst case at this size is isolated — every sort keeps between 41% and 69% of its excess one swap away — and that the size of a single swap’s effect varies by a factor of two between sorts. Whether a peak is narrow is a question about larger inputs.

Sorted input’s two thousand neighbours #

At sixty-four elements the neighbourhood of sorted input is still small enough to count in full: 2,016 single swaps, each run through first-element quicksort.

One swap, chosen well, removes 65% of the worst case; the average swap removes 24%. The position of the swap matters more than anything else about it. The 63 swaps that involve the first position average 1,047.1 comparisons, about half the worst case, because they change the very first partition, which is the one that runs over the whole array. Swaps confined to the end of the array are met only when the ranges are already short, and every one of the 63 swaps that change nothing at all involves the last position.

So sorted input is a peak whose flanks fall steeply where the front of the array is disturbed and hardly at all where the back is. That does not mean only the front matters. On sorted input the recursion’s ranges are the suffixes of the array — the first partition takes everything, the next everything but the first element, and so on — so every position is the front of exactly one range, and a disturbance anywhere lands at the front of some range. What position decides is how long that range still is when the disturbance is met.

Disorder at two thousand elements #

Above sixty-four the neighbourhood cannot be listed and has to be sampled, and the natural way to sample it is to apply a stated amount of disorder. The model here is the one used in the smoothed analysis of quicksort by Banderier, Beier and Mehlhorn. Each position of the input is marked independently with probability $p$, and the values at the marked positions are shuffled among themselves. At $p = 0$ the input is the worst case untouched; at $p = 1$ it is a uniformly random ordering; and in between, $p$ is the fraction of the input that has been disturbed.

Each sort is given the most expensive input known for it: sorted input for first-element quicksort and reversed input for insertion sort, both worst cases by argument; for merge sort the input McIlroy’s adversary settles on, which costs exactly the worst case’s formula; and for median-of-three quicksort the adversary’s input too, which is quadratic but not known to be the worst.

Four lines, four different kinds of worst case.

Merge sort’s is flat on the floor. A worst case three per cent above the average is not a hazard at any level of disorder, and the plate would not distinguish it from its average without the numbers.

Insertion sort’s barely moves. Reshuffling one per cent of a reversed array leaves insertion sort doing 1.99 times its average; reshuffling ten per cent leaves 1.88. Half the array reshuffled still costs 1.42 times the average. This is a worst case that data does not have to find exactly. Any input that is mostly in reverse order is most of the way to it.

The two quicksorts’ fall off a cliff, and the cliff starts almost at once. At $p = 0.001$ — on average two of the 2,048 positions reshuffled — first-element quicksort has already lost fourteen per cent of its excess. At $p = 0.01$ it is down from 82 times the average to 26.5; at $p = 0.05$, to under nine. The adversary’s input for median-of-three quicksort is more fragile still: twenty reshuffled positions take it from 41 times the average to under seven.

That last point deserves a sentence of its own, because it says what the adversary’s inputs are. They are built comparison by comparison to exploit a pivot rule exactly, and the construction leaves nothing to spare. The adversary who knows the seed argued that a published function can be attacked; this plate adds that the attack has to be delivered precisely, because a one per cent perturbation of the attack’s input removes 86% of its effect.

The mean hides a lottery #

A mean over twelve shuffles is a summary, and on average is not a number is this collection’s standing objection to letting one stand alone. At small $p$ the summary is hiding something specific: whether the few reshuffled positions happened to land where they matter.

At $p = 0.002$ — about two positions of 1,024 — two runs in three keep nearly the whole worst case, and the cheapest loses two-thirds of it. The distribution is not a hump around a centre but a pile against the ceiling with a long tail below it, and the mean sits below the pile, pulled down by the tail. That is what a narrow peak looks like when it is sampled: most small disturbances miss the places that matter, and the ones that hit them hit hard.

By $p = 0.01$ — about ten positions — the pile has left the ceiling. Two runs in 120 keep 90% of the worst case and one of them keeps all of it; the middle of the cloud is near half of it, and the range spans a factor of five. By $p = 0.05$ nothing is near the worst case, and the cheapest runs are within a factor of about three of random input.

Ten positions, at every size #

The plates put the halving of first-element quicksort’s worst case near $p = 0.01$ at 1,024 elements and a little above $p = 0.005$ at 2,048, and that ratio is suggestive. The measurement below finds the halving point by bisection at five sizes.

The fraction falls by a factor of fourteen across a sixteen-fold range of sizes. The number of positions barely moves: between ten and thirteen at every size, with no trend the twelve-shuffle noise could not account for. A constant number of disturbances halves the worst case, not a constant fraction — and so, measured as a share of the input, first-element quicksort’s worst case gets narrower in exact proportion as the input grows.

The mechanism is visible in the plates above even though it is not proved here. The quadratic cost of sorted input comes from ranges whose first element is extreme, and a reshuffled value that reaches the front of a large range splits it at a random point instead. What matters is how many such splits happen early, while the ranges are still long, and that is a matter of how many values were reshuffled — not of what fraction of the array they were. A range of two thousand sorted elements and a range of two hundred are equally undone by a handful of splits.

The smoothed analysis that introduced this model bounds quicksort’s expected count by a constant times $(n/p)\log n$, and it is worth being exact about what that bound does and does not say here. At ten positions, $p$ is $10/n$ and the bound becomes a constant times $n^2 \log n$, which grows faster than the quadratic count it is bounding; in this regime the bound says nothing at all. It becomes informative when the number of reshuffled positions is large compared with $\log n$, which is where the plate’s lines have already flattened towards the average. So the constancy measured here is a fact about sizes 128 to 2,048 and twelve shuffles a point. Whether it holds at a million elements, or rises slowly with $n$ in a way this range is too short to show, is not settled by anything on this page.

Insertion sort’s worst case is a region #

Insertion sort’s line on the first plate was nearly flat, and unlike quicksort’s it can be predicted exactly. Its comparison count is the number of inverted pairs in its input plus at most $n - 1$, so the question is how many pairs of a reversed array remain inverted after a fraction $p$ of positions is reshuffled.

Two unmarked positions keep their values and stay inverted. Two marked positions receive two values drawn from the shuffle and are inverted half the time. A pair with one marked and one unmarked position is the case that needs care: the marked position gets a value drawn uniformly, and the unmarked one keeps a value set by where it sits. An unmarked position near the front of a reversed array holds a large value, so a random value placed after it is usually smaller and the pair stays inverted; one near the back holds a small value and the pair usually becomes ordered. Averaged over all pairs, the first kind outweighs the second, and a mixed pair stays inverted two times in three. Adding the three cases gives the share of pairs still inverted as $(1-p)^2 + \tfrac{4}{3}p(1-p) + \tfrac{1}{2}p^2 = 1 - \tfrac{2}{3}p + \tfrac{1}{6}p^2$.

The dots sit on the solid curve at every $p$ — within three-tenths of a per cent up to $p = 1/2$, and within one per cent at $p = 1$, where the $n - 1$ comparisons the pair count leaves out are largest in proportion. The dashed curve, which is what the natural first guess — a disturbed pair is a coin flip — produces, is 12% too low at $p = 1/2$. The checks hold insertion sort’s count to the first curve at four values of $p$ and require the second to be refused by the same measurements, which it is.

The curve’s slope at $p = 0$ is the result that matters for data: two-thirds. Disturbing one per cent of a reversed array removes two-thirds of one per cent of insertion sort’s work. Nothing about the size of the input enters. The worst case is not a point with a neighbourhood but a region with a gentle floor, and what O-notation does not say about insertion sort — that its class is a statement about some inputs rather than all — applies to every input that is mostly reversed, not to one.

What each worst case warns about #

The four lines on the first plate call for four different reactions, and none of them is visible in the four worst-case numbers alone.

First-element quicksort’s worst case is a warning about exact order. It is enormous — 82 times the average — and about ten positions wide. Data that is sorted exactly, or sorted except at the end, hits it in full. Data with even a few dozen displaced elements at scale has lost most of it. That is why the defences are so cheap. What randomising the pivot buys moves the pivot off the one position the peak is balanced on, and the pattern that defeats the pattern measures a deterministic version that swaps a handful of elements at fixed positions when a partition looks suspicious — which is this page’s ten positions, applied on purpose. The sort the library ships is where both ideas ended up.

Median-of-three quicksort’s worst case is a warning about an opponent. No data wanders into an input built comparison by comparison against a pivot rule, and a one per cent perturbation of that input removes most of its effect. It is a hazard exactly where somebody is constructing inputs on purpose, which is the setting the depth limit that almost never fires was designed for.

Insertion sort’s worst case is a warning about order in bulk. Its famous input is one of a broad region, and any data that runs mostly the wrong way is most of the way to it. A run is a property of the input argued that “nearly sorted” should be a measured quantity rather than a recipe; the pair count on this page is such a quantity for “nearly reversed”, and it predicts insertion sort’s cost from it exactly.

Merge sort’s worst case is not a warning about anything. A quarter of all orderings reach it at eight elements, and it is three per cent above the average at two thousand.

Still open: a sort for which every input is the worst #

The widths on this page ran from ten positions to a quarter of all inputs. There is a limit further out still: a sort for which every input costs the same, so that the set of worst inputs is all of them, the distance plot is a flat line at the top, and a benchmark cannot choose a bad input because there is none to choose.

Such sorts exist and are used. A sorting network fixes in advance which pairs of positions it will compare, in which order, and never lets the answer to one comparison decide which comparison comes next. Its comparison count is a property of $n$ alone, identical on sorted, reversed, adversarial and random input. That removes every question this page asked — and it costs something the sorts here never pay, since a sort that cannot adapt its questions to the answers must ask enough questions for every input at once. How much more that is, measured against the enumerated distributions of the adaptive sorts, is the next measurement.