The worst case found by climbing

A count over every input ran five sorts on all 40,320 orderings of eight elements and read each one’s worst case off the complete list. For three of the five the worst ordering was one no benchmark input family produces, and for median-of-three quicksort every named input landed on the best case. The method was exhaustive, and exhaustion stops being available almost immediately: ten elements have 3.6 million orderings, twelve have 479 million, and sixty-four have more orderings than there are atoms in the observable universe by a factor of about $10^{9}$.

Above a dozen elements, then, a worst case has to be searched for. There are two families of search and they differ in what they know. A local search knows nothing about the algorithm. It holds an ordering, changes it a little, runs the sort, and keeps the change if the count went up. An adversary knows exactly how one family of algorithms chooses what to compare and answers each comparison so that the choice turns out badly. The first applies to any sort; the second applies to the sorts it was written against.

Both produce an input, and an input is a claim: this ordering costs at least this much. What neither produces on its own is the other half of a worst case, the statement that nothing costs more. This page runs both kinds of search against the same five sorts, checks them at the size where the true answer is on file, and then follows them to sizes where it is not — keeping, wherever one exists, a worst case that is known exactly by argument, so that the search can be marked rather than trusted.

A climb, scored against the enumeration #

The local search here is the simplest one worth the name. Start from a random ordering. Pick two positions uniformly and swap them. Run the sort and count its comparisons. If the count rose, keep the swap; otherwise undo it. Repeat.

One variation matters more than any other, and it is whether a swap that leaves the count unchanged is kept. A strict climb refuses it and so stops at the first ordering none of whose neighbours is better. A climb that accepts ties can walk across a level stretch — a plateau of orderings that all cost the same — and find a rise on the far side of it. The difference sounds like a detail of tuning and at eight elements it is the difference between a search that finds worst cases and one that usually does.

The plate has the answer that the count over every input asked for when it proposed this experiment. That essay set the test precisely: if a climb finds 29 for heapsort from a random start, it is finding worst cases; if it stalls at 27, it is finding what the benchmark found. Every one of two hundred climbs that accept ties finds 29. So does every one on median-of-three quicksort, and so does all but one on first-element quicksort.

The strict climbs are the useful contrast. More than a quarter of them fail on heapsort, one in eight on first-element quicksort, and one in six on median-of-three quicksort. An ordering where no single swap raises the count, but some swap leaves it level and a later swap raises it, is common at this size, and a search that cannot cross it reports the edge of the plateau as the top.

By the only standard available at eight elements, then, the climb that accepts ties works: it finds the enumerated worst case for all five sorts from almost every start, within two hundred swaps. The question the rest of this page is about is what that result entitles anyone to say about a larger input.

A worst case that is known by argument #

Two of the five sorts have worst cases that are not searched for or enumerated but derived. Insertion sort makes at most $n(n-1)/2$ comparisons, on reversed input, and so does quicksort with the first element as its pivot, on sorted input. Top-down merge sort, splitting a range of $n$ at $\lfloor n/2 \rfloor$, makes at most $n\lceil\log_2 n\rceil - 2^{\lceil\log_2 n\rceil} + 1$, a count reached when every merge at every level interleaves its two runs to the last element. At 256 elements that is 1,793.

These three are what make it possible to follow the climb past the size where enumeration ends and still mark its work. A climb that reaches 1,793 on merge sort at 256 elements has found a worst case, and this is known without looking at any other ordering. A climb that stops at 1,780 has not, and this too is known.

On merge sort the climb works at 256 exactly as it worked at eight. Every run reaches the formula’s value, the slowest within two and a half thousand swaps, and none of them goes past it — which the formula guarantees and which the figure’s own check requires.

The shape of the curves says why. Merge sort’s comparison count is a sum over its merges, and each merge’s contribution depends on how the elements of its two runs interleave. A swap that makes one more pair interleave in one merge raises that merge’s cost by one and, most of the time, disturbs no other merge. Improvements accumulate. The count’s landscape over orderings is close to a sum of small independent landscapes, and a climb on such a thing only has to keep finding a rise somewhere, which it always can until it is at the top.

The same climb, at sizes the check cannot reach #

The climb checked at eight elements can now be run on all three sorts whose worst cases are derived, at sizes between eight and sixty-four, scored against the exact value at each size.

Two of the three lines are flat at the top of the frame. The third falls off it between twelve and sixty-four elements, and by sixty-four the typical climb reaches about 790 comparisons of the 2,016 that sorted input costs.

The difficulty is not that first-element quicksort’s worst case is obscure. It is the most famous worst case in sorting. Every textbook that introduces quicksort warns that taking the first element as pivot makes sorted input quadratic, every benchmark generator produces sorted input partly because of that warning, and what randomising the pivot buys measures the remedy on this very input: 130,816 comparisons at 512 elements with the first element as pivot, 5,490 with a random one. A benchmark finds this worst case trivially. A search that knows nothing about quicksort does not find it at all.

And the search was validated. At eight elements it found first-element quicksort’s worst case from 199 of 200 starts; at twelve, from 23 of 24. A reader shown only the check at eight would have every reason to trust the search at sixty-four, and would be trusting a method that reports about 790 as the worst case of an algorithm whose worst case is 2,016.

What the climb stopped on #

There are two ways a climb can fall short, and they call for different repairs. It can be on a long slope whose rising swaps are simply rare, so that more swaps would eventually get it there. Or it can be on a local maximum, an ordering where no swap raises the count at all, so that no number of swaps will. The long climb below, and a count of what it had available, show that first-element quicksort’s landscape is something between the two.

Sixteen times the budget helps, and it does not help enough. The second climb spends its last 38,000 swaps without a single rise, 731 comparisons short of the worst case. The first is still rising at the very end, but at 1,139 it has reached 57% of the worst case, and its gains come further and further apart.

Counting what the first climb had available answers the question directly. At eleven points during the climb, every one of the 2,016 single swaps of the ordering it had reached can be run through the sort, and the number that would raise the count read off.

The rises run out, and not smoothly — fifteen at 800 swaps and twenty-two at 1,600, because walking across a level stretch sometimes lands on an ordering with more rises than the one before it. From 25,600 swaps on there are none: every one of the 2,016 possible swaps of the ordering reached either lowers the count or leaves it where it is. The climb goes on rising only because it accepts level swaps. Between 25,600 and 102,400 swaps it gains another 207 comparisons by wandering across orderings that all cost the same until one of them happens to have a rise, and at the end one of its 21 level swaps still leads to such an ordering.

That is not quite a local maximum. It is a plateau with an exit, and the exits become rarer as the climb gets higher — which is why sixteen times the swaps bought so little, and why a search that finds merge sort’s worst case within a few thousand swaps is at 57% of this one after a hundred thousand.

Why quicksort’s landscape traps a climb where merge sort’s does not is not proved here, and the measurement suggests the mechanism. First-element quicksort’s cost is the sum, over every call, of the size of the range it partitions, so it is large when the element at the front of each range is extreme in that range. Which elements form a range, and in what order, is decided by every partition above it — the partition moves elements as it goes. A swap that makes the front of the whole array more extreme reorganises every range below it, so an improvement at one level is routinely paid for at another. Merge sort’s merges are fixed by position and do not rearrange each other’s inputs. One landscape is nearly a sum of parts; the other is a chain in which each part rewrites the next.

An adversary that answers the questions #

The depth limit that almost never fires introduced McIlroy’s adversary, which does not search over orderings at all. It is the same device the adversary who hides the edge uses to prove a lower bound — an opponent that answers questions so as to keep the algorithm working — pointed at one algorithm instead of at all of them, so that it builds an input rather than a floor. It hands the sort placeholders whose order is undecided, and whenever two undecided placeholders are compared it fixes one of them as the next-smallest value and leaves the other undecided, so that whatever the sort picks as a pivot turns out to be larger than everything it is compared with. At the end of the run the decisions it made form an ordinary array, and replaying the sort on that array must cost exactly what the live run cost — which the figure below checks for every sort, since an adversary that answered inconsistently would have described no input at all.

That essay aimed the adversary at one library sort. Here it is aimed at all five, beside the climbs.

No search wins every row, and the pattern of who wins is the useful result.

The adversary is a construction for quicksort, and on quicksort nothing else comes close. Against first-element quicksort it builds a quadratic input, 32,640 comparisons, where the climb from a random start reached 3,923. Against median-of-three quicksort it builds an input costing 16,768 — half of $n(n-1)/2$, quadratic in its own right — where the best climb reached 3,947 and the best named input 2,911. Median-of-three quicksort was introduced to defeat sorted input and does defeat it; its own quadratic case is an input none of the named input families produces and no climb found, and the adversary builds it in one run.

Off its own family the adversary is worse than useless. On insertion sort it builds an input costing 255 comparisons, which is $n-1$, the best case. Its rule — an undecided element compares greater than a decided one — tells insertion sort that each new element is larger than everything before it, which is exactly sorted input. On heapsort it builds an input costing 3,106 — the same as reversed input, and below both the climb and the sorted input a benchmark would try first. It happens to hit merge sort’s formula exactly.

The climb is general and weak. It finds merge sort’s worst case, nearly finds insertion sort’s, and on both quicksorts falls far short of a construction that knows the pivot rule. Started from the most expensive named input instead of from a random ordering, it never does worse than that input — it can only rise — and on median-of-three quicksort it raises 2,911 to 3,947, which shows that seeding a search with the benchmark’s own inputs is cheap insurance and still nowhere near enough.

Heapsort, where nothing marks the search #

Heapsort is the row with no known worst case. No formula gives it at 256 elements, and enumeration is out of the question, so every number a search reports is a lower bound on the worst case. The only upper bound comes from counting the most each step could cost, and it is drawn as a dotted rule.

Two of the three climbs end below sorted input. A search that ran on its own, from random starts, would report 3,399 as the most expensive ordering it found — lower than the most obvious input anyone would test. The climb from sorted input does better than sorted input by 42 comparisons, about 1%, and there is no way to know from these curves whether 3,494 is close to the truth or a local maximum a long way below it. The first-element quicksort climbs say how much a curve like this can hide.

What can be said about heapsort’s worst case at 256 is therefore a pair of inequalities. From below, the best climb: at least 3,494. From above, the sort’s own structure. Building the heap sifts each node down at most its height, two comparisons a level, and those heights sum to 255, so building the heap costs at most 510. Each of the 255 extractions then sifts from the root through at most $\lfloor\log_2 e\rfloor$ levels of a heap of $e$ elements, which adds up to 3,076. The ceiling is 3,586. The floor under every comparison sort gives a third number, $\lceil\log_2 256!\rceil = 1{,}684$, which no sort’s worst case can be under and which heapsort is nowhere near — how close anything gets to the floor measures it at nearly twice the floor on random input.

So the worst case is between 3,494 and 3,586, a window of 92 comparisons, and nothing on this page narrows it. The ceiling is not tight either. At eight elements the same sum gives 34 and the enumeration says the true worst is 29; a ceiling built from the most every step could cost assumes every step costs its most at once, which the steps of one run cannot all do.

What a check at eight elements certifies #

The standard a method has to meet here is that it is checked against something that could have disagreed — fitting a class to measurements grants a complexity class only when the fit could have refused it — and the climb was. At eight elements it was held against the enumeration and it passed, for every sort, from nearly every start. The checks behind the plates go further than the plates: twelve climbs of four hundred swaps per sort must reach the enumerated worst case at eight elements, and six climbs at sixty-four must fail to reach first-element quicksort’s — so that if the search ever began succeeding there, the argument of this page would have to be rewritten and something would say so. And a climb’s result at sixty-four offered as a certified worst case is refused, because the one number that can refuse it is on file. The check must reject is the standard that last check is held to.

What the passing check at eight certified was that the search finds worst cases in landscapes as small as eight elements make them. A landscape of 40,320 orderings in which each ordering has 28 neighbours is small enough that maxima are rare and plateaus short. The landscape at sixty-four is not a larger copy of it. It has plateaus whose exits are too small to find, which eight elements are too small to contain, and first-element quicksort’s is the one that happens to be measurable because its true worst case is known for another reason.

The general form is uncomfortable and worth stating plainly. A search method validated at the sizes where answers can be checked has been validated on a different problem from the one it is then used for. The failures that matter — local maxima, long plateaus, landscapes that rearrange themselves — are properties of scale, and the small sizes lack them. The same is true of any test on small instances, and it is why a limit is not a prediction insists on stating the range a fit was taken over.

What to keep from each search #

Three things follow, and each is checkable against the plates.

Report a searched worst case as a lower bound, with the method. “Heapsort costs at least 3,494 comparisons on some ordering of 256 elements, found by a swap climb from sorted input” is true and informative. “Heapsort’s worst case at 256 is 3,494” is a claim nobody on this page can support. A guarantee is not a result, and a result is not a guarantee either.

Run constructions for the families that have them. For any sort that picks a pivot by comparing a few elements, McIlroy’s adversary costs one run and found inputs no climb approached. It is also a hazard: pointed at the wrong family it builds the best case, so its output has to be read against the other searches, not instead of them.

Seed searches from the inputs that are already known to be bad, and keep the known formulas as scorekeepers. A climb from sorted input never reports less than sorted input costs, and the pattern that defeats the pattern is the record of why the known-bad inputs deserve that place: each was added to the list because some sort once failed on it. And the few sorts with exact worst cases — merge sort, insertion sort, first-element quicksort — are the only places where a search can be caught failing at a realistic size, which makes them worth running every search against before it is trusted on a sort that has none.

Still open: whether a worst case is a point or a neighbourhood #

Sorted input is first-element quicksort’s worst case, and a climb from a random start could not find its way there. That suggests something about sorted input itself: if the orderings around it were nearly as expensive, a climb that got close would be pulled in. The climb’s failure hints that they are not — that the worst case is a narrow peak, and that orderings a few swaps from it cost much less.

That is a measurable claim with a practical edge. Real data is often nearly sorted — sorted by something, then appended to, or mostly in order with a few late arrivals — and a worst case that a little disorder destroys is a very different hazard from one that survives it. Insertion sort’s worst case, reversed input, should behave the other way: its cost is the number of out-of-order pairs, and scrambling a small fraction of a reversed array leaves most pairs reversed. The next measurement takes each sort’s worst case, re-shuffles a stated fraction of its positions, and asks how quickly the count falls towards the average — which is the question expected is not average asks of a random pivot, asked of the input instead.