A count over every input

A distribution computed rather than sampled removed the uncertainty from a randomised algorithm’s count by weighing every random choice exactly. This page does the same thing to the other source of variation in a count: the input.

A deterministic sort’s comparison count is a function of the order its input arrives in. The usual way to report that function is to evaluate it at a few named points. A benchmark generator produces sorted input, reversed input, nearly sorted input with a few elements displaced, random input, and input with few unique values — and a table reports each sort’s count on each. The count somebody chose found that even the choice of what to count is a decision a reader is rarely shown; the choice of which inputs to count it on is another.

At small sizes the function can be evaluated everywhere. Eight elements have 40,320 orderings. Every one can be run through every sort, and the count’s best, mean and worst read off exactly — not estimated, and not reached by a clever construction, but found by looking at all of them. The named inputs can then be placed among the whole population, and the question asked of each: is it where the interesting behaviour is?

Six elements first #

At six elements the pattern is already there, in a smaller form. Two of the sorts have a worst case that a named input reaches — insertion sort and first-element quicksort, both on reversed or sorted input — and three do not. For those three the gap is a single comparison, which at six elements is the smallest gap there can be, and it would be easy to dismiss.

Eight elements #

At eight elements the three gaps are one, two and four comparisons, and the last one is the result to look at first.

Median-of-three quicksort never makes fewer than 25 comparisons on eight elements and sometimes makes 29. Every one of the five named inputs gives exactly 25. A benchmark that ran this sort on its standard inputs would report a constant 25 comparisons, flat across sorted, reversed, nearly sorted, random and few unique, and would conclude that the sort’s cost does not depend on its input. Its mean over all inputs is 26.30 and its worst is 29, 16% above everything the benchmark saw.

Heapsort runs from 21 to 29 and the named inputs reach 27. Merge sort runs from 12 to 17 and the named inputs reach 16.

Insertion sort and first-element quicksort are the two sorts whose worst cases the named inputs do find, and they are the two whose worst cases are famous: insertion sort’s is reversed input, at $n(n-1)/2 = 28$, and first-element quicksort’s is sorted input, at the same 28. The named inputs were chosen, historically, because they find those worst cases. They find them and nothing else.

What the worst cases look like #

Merge sort’s worst case has a recognisable structure once it is found. A merge makes the most comparisons when the two runs it merges interleave — when the smallest remaining element alternates between them to the end — because then neither run is exhausted early and every element costs a comparison. The ordering [0, 2, 1, 6, 3, 5, 4, 7] is built so that every merge at every level interleaves. Its count, 17, is exactly the published worst case for a top-down merge sort on eight elements, $n\lceil\log_2 n\rceil - 2^{\lceil\log_2 n\rceil} + 1$.

Sorted and reversed input are merge sort’s best case, at 12, because every merge of two runs where one lies entirely below the other stops comparing as soon as the lower run is used up. A benchmark’s “hard” input for insertion sort is merge sort’s easiest. Random input lands at 16, the mode of the distribution — which is what random input should do, and which is exactly why it never finds a tail.

That point generalises. A random input is a draw from the bulk of the distribution, and a worst case is in its tail. At eight elements merge sort’s worst case is the thin spike at the right of the histogram, reached by a small fraction of the 40,320 orderings, and a random input lands on one of them only by luck. As $n$ grows the worst-case orderings become a vanishing fraction, and a random input’s chance of hitting one goes to zero. So “random” in a benchmark measures the mean and says nothing about the worst, and the named structured inputs measure the worst only for the algorithms they were designed against.

Heapsort is the sort for which the named inputs are least informative, because its behaviour is least tied to presortedness. It rebuilds its input into a heap first, and a heap built from sorted input is a particular heap, not an especially good or bad one. Its count spreads roughly symmetrically from 21 to 29, and the named inputs land in the middle of that range: reversed input, which is already a max-heap, is below the mean at 24, and sorted input is above it at 27.

The worst ordering, [0, 3, 1, 5, 4, 2, 6, 7], has no presortedness property a generator would name. It is simply the ordering that makes the heap’s sift-down paths longest, and it can only be found by looking.

The two quicksorts #

First-element quicksort is the case where the benchmark works, and it works for the reason given above: sorted input was put in benchmarks to catch exactly this sort. Every pivot is the smallest remaining element, every split is maximally uneven, and the count is $n(n-1)/2$.

This plate also carries an identity that the rung before this one predicted. The mean over every input is 16.921 — to the digits the plate reports, the same number as the expected comparison count of quicksort with a random pivot on eight elements. That is not a coincidence and not an approximation. Averaging first-element quicksort over every ordering of the input is the same sum as averaging random-pivot quicksort over every choice of pivots on one fixed input, because a uniformly random ordering makes the first element a uniformly random pivot at every level. The distribution computed exactly there and the enumeration performed here are two routes to one number, and the site’s checks reach it both ways.

That identity also explains what randomising the pivot buys and what it does not. It does not lower the mean — the mean is 16.92 either way. It moves the randomness from the input to the algorithm, so that no particular input is bad. What randomising the pivot buys measured that trade on real implementations, and the plate says precisely what is being traded: a tail of bad inputs, fixed and findable, for a tail of bad runs, random and not.

Median-of-three quicksort was designed to defeat the first-element sort’s worst case, and on the named inputs it succeeds completely: sorted and reversed input give it a perfect median at every level, since the first, middle and last elements of a sorted range are its minimum, median and maximum. Nearly sorted input is close enough to sorted to behave the same way.

The worst ordering, [0, 1, 2, 5, 3, 4, 6, 7], is sorted except for a small disturbance placed so that the three sampled positions give a poor median. It is exactly the kind of input a designer who knew the pivot rule would construct, and none of the standard inputs is that kind. The pattern that defeats the pattern is the same story at scale, for production sorts whose pivot rules are defeated by inputs built to match them, and the eight-element enumeration shows the mechanism in its smallest complete form.

What exhaustive enumeration is for #

Forty thousand orderings of eight elements is not a size anyone sorts. The point of enumerating it is not the numbers at eight but what the enumeration can do that no other method can.

It finds worst cases nobody has to imagine. Every worst-case ordering above was found by looking at all orderings, not by reasoning about the algorithm. That matters most for heapsort’s, which has no structure a generator would think to produce, and for median-of-three quicksort’s, which has structure only relative to a pivot rule the generator did not know about.

It gives the whole distribution, so the mean is exact and the tail is visible. The floor under every comparison sort proves that no comparison sort can average fewer than $\log_2 n!$ comparisons over all inputs — 15.30 at eight elements. The enumeration measures how close each sort comes: merge sort’s mean of 15.73 is within three per cent of the floor, first-element quicksort’s 16.92 within eleven, and median-of-three quicksort’s 26.30 is 72% above it, paying heavily in the average for defence against one worst case.

It is a check that could fail. The site’s check requires that each named permutation’s count lies within the enumerated best and worst — which it must, since a named permutation is one of the orderings — and that insertion sort’s worst case is exactly reversed input and first-element quicksort’s exactly $n(n-1)/2$. An implementation with an extra comparison in its inner loop would violate the second, and one that miscounted would violate the first. The check must reject is the standard these are held to.

What it cannot do is scale. Ten elements have 3.6 million orderings and twelve have 479 million, and every sort must run on every one. Enumeration is a microscope for small $n$, where it shows the shape of each sort’s input dependence, and that shape — which kinds of input are extreme — is what carries to larger sizes, while the numbers do not.

Why the named inputs are the ones they are #

The five named inputs were not chosen from a principle. Each was added to benchmark suites because some sort had failed on it, and a list of standard inputs is therefore a record of past failures rather than a sample of possible ones.

Sorted and reversed input catch the oldest failures: insertion sort’s quadratic behaviour, and quicksort implementations that took the first or last element as pivot and went quadratic on data that was already in order — a common state for real data, since data is often sorted by something already. Nearly sorted input came with adaptive sorts, whose selling point was speed on data with long runs, and the sort the library ships is this collection’s measurement of what such sorts gain on it. Few unique values catch partitioning schemes that degrade when many elements equal the pivot, which three-way partitioning fixed. Random input is the control.

Each input is the right test for the failure it was added to catch, and the plates show each catching it. What the list cannot do is catch a failure nobody has had yet, and the median-of-three pivot rule is the clean example: it was introduced to defeat sorted input, it defeats it perfectly, and its own worst case is an input that the list — built before the rule existed — has no reason to contain. A benchmark suite always lags the algorithms it tests by exactly one design.

There is a practical defence, and the enumeration suggests it. Alongside the named inputs, a benchmark can include inputs derived from the algorithm under test — the worst ordering found by enumeration at a small size, scaled up by repeating its pattern — so that each sort is measured against an input built for it as well as against inputs built for its predecessors. For merge sort that scaled input is the fully interleaved ordering; for median-of-three quicksort it is sorted data with a disturbance placed at the positions the pivot rule samples. Neither is exotic, and neither is on the standard list.

The inputs that are not permutations #

One of the five named inputs is not in the population the enumeration covers. Few-unique input has repeated values, and the 40,320 orderings are orderings of eight distinct values. The site’s check therefore holds only the other four named inputs to the enumerated range, and the plates show few-unique input landing inside it anyway.

That is not guaranteed in general. A sort on input with repeated values can make fewer comparisons than on any permutation — a three-way partition finishes a run of equal elements in one pass — or more, if its equality handling is poor. The floor when the values repeat measures how far the information-theoretic floor itself drops when values repeat, and it drops a long way: a sort on few distinct values has less to find out. So few-unique input tests a different question from the other four, about how a sort treats equality rather than how it treats order, and placing it on the same axis as permutations is a convenience of the plate rather than a claim that it belongs there.

What a benchmark should take from this #

Three things, each checkable against the plates.

Name the property each input tests. Sorted input tests adaptivity for insertion sort and the pivot rule for first-element quicksort. It tests nothing in particular for heapsort and gives median-of-three quicksort its best case. A table that reports all five sorts on sorted input implies it is the same test for all five, and one set, three orders is this collection’s warning that the order of an input is an assumption about the algorithm it is fed to.

A random input measures the mean, not the spread. The random input on every plate above lands near the mode. A benchmark that reports “random” as its general case reports the centre of the distribution; the tail needs either many random inputs and a report of their spread, or inputs built against the algorithm.

A worst case is a property of an algorithm and an adversary together. A guarantee is not a result: a sort’s published worst-case bound holds whatever the input, and a benchmark’s “worst observed” holds for the inputs somebody thought of. The enumeration here found three sorts for which those two numbers differ at eight elements, and for one of them the benchmark’s number was the best case.

Where this ladder goes next: the worst case found by search #

Enumeration stops at a dozen elements. Above that, a worst case has to be found by searching the space of orderings rather than listing it, and the searches that work are adversarial rather than random.

The standard construction for quicksort is an adversary that answers comparisons lazily, deciding the relative order of elements only when the algorithm forces it, and always answering so that the pivot is as bad as possible — which builds, as the sort runs, an input the sort was bound to perform badly on. For sorts without such a construction, a local search — start from a random ordering, swap two elements, keep the swap if the count rises — climbs towards high counts. The next rung runs both against the five sorts at sizes enumeration cannot reach, and checks the search against the enumeration at eight elements, where the true worst is known: if a search 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.

The lazy adversary is also the construction behind a whole family of lower bounds. The adversary who hides the edge uses an adversary that answers an algorithm’s questions so as to keep it ignorant as long as possible, and proves a floor from how long that takes. Pointed at a specific algorithm instead of at all algorithms, the same adversary stops proving a floor and starts constructing a bad input — which is the step from a bound to a benchmark that this ladder has been working towards.