The sort whose count has no distribution

A worst case ten positions wide measured how many inputs share each sort’s worst case, and the answers ran from 128 orderings of eight elements for first-element quicksort to 10,240 for merge sort. It closed on the limit further out than either: a sort for which every input is the worst case, because every input costs the same.

Such a sort is not a curiosity. Every sort measured so far adapts. Which pair of elements it compares next depends on the answers to the comparisons it has already made — merge sort takes from whichever run won, quicksort sends an element left or right of the pivot, insertion sort stops walking when it finds a smaller element. That dependence is where every distribution on the site comes from, because different inputs give different answers and different answers lead to different questions.

A sorting network gives it up entirely. It is a list of pairs of positions, fixed by the number of elements alone and written down before any input exists. Each pair is compared and, if its two elements are out of order, exchanged. The list is carried out in full whatever the answers are. So its comparison count is not a random variable, not a function of the input, and not a worst case — it is the length of the list. This page measures what that costs, what it buys, and which count it does not fix.

Nineteen on every ordering #

A count over every input ran five sorts on all 40,320 orderings of eight elements. Batcher’s odd–even merge network, run on the same 40,320, can be set beside them.

The network’s row is a single mark, and where the mark falls is the first surprise. Nineteen comparisons on every input is more than merge sort ever makes — two above merge sort’s worst case of 17 — and it is less than heapsort ever makes, two below heapsort’s best case of 21. It is below median-of-three quicksort’s best by six. It is under insertion sort’s average of 19.28 and nine under insertion sort’s worst.

So at eight elements a fixed plan is not a bad plan. Two of the five adaptive sorts are beaten by it on every single input, and a third is beaten on average. What the adaptive sorts gain by choosing their questions is real — merge sort’s worst case is two comparisons better — but the gain is small, and three of the five do not capture it.

The floor under the plate is the one the floor under every comparison sort proves: $\lceil\log_2 8!\rceil = 16$, which no comparison sort’s worst case can be under because a sort’s comparisons must distinguish all 40,320 orderings and sixteen yes-or-no answers are the fewest that can. An adaptive sort can reach it — merge insertion, the Ford–Johnson algorithm, sorts eight elements in sixteen comparisons at worst — and a network cannot, because a network must ask enough questions for every input at once. Nineteen is known to be the fewest comparators any network on eight positions can use, so the three comparisons between sixteen and nineteen are the exact price, at this size, of not letting one answer choose the next question.

A plan written before the input #

A network is easiest to understand drawn. Batcher’s construction sorts each half of the positions by the same construction and then merges the two sorted halves with a fixed merging network, which itself works by merging the even-numbered positions and the odd-numbered positions separately and then fixing up neighbours.

The picture is the whole algorithm. There is no branch in it, no loop whose length depends on data, and nothing that could be done differently on a different input.

It also carries its own count. Reading the drawing from the right, the last four rounds are a single merging network, taking two sorted runs of eight and producing one sorted run of sixteen. Before them sit two copies of the network for eight positions, one on the upper half and one on the lower, running side by side; before those, four copies of the network for four; and so on down to comparators on neighbouring pairs. A merging network for two runs of $m$ first merges their even positions and their odd positions separately — two merges of runs half as long, which can run at the same time — and then compares $m - 1$ pairs of neighbours in one final round. So merging two runs of $m$ takes one round more than merging two runs of $m/2$, and $\log_2 m + 1$ rounds in all; at sixteen positions the four levels of merging need 1, 2, 3 and 4 rounds, which is the ten on the plate. The comparators follow the same recurrence, and the two recurrences give the formulas the next plate is checked against. Nothing in either depends on the input, which is why a formula is available at all: for an adaptive sort the same derivation produces a worst case, and the next section’s comparison is between a count and a bound.

Two properties follow directly from the fixed plan, and neither has any analogue in the sorts measured so far.

The first is that the comparisons can be scheduled. Comparators that share no position do not interfere, so everything in one round could be carried out at the same moment, by separate circuits or separate processor cores or the separate lanes of a vector instruction. The network on sixteen positions finishes in ten rounds. The order that has a depth measured the same quantity for filling a table — the longest chain of work that must happen in sequence — and found that a count of total work cannot see it. An adaptive sort does not even have a depth in this sense, because which comparison it makes second is not known until the first has been answered.

The second is that the comparisons need no branches. A comparator can be written as “put the smaller of these two here and the larger there”, which a processor computes without a conditional jump at all. A search with no branch to miss paid extra comparisons to remove branch mispredictions from binary search. A network has no mispredictions to remove, and vectorised sorting routines sort their short base cases with small fixed networks for exactly these two reasons.

What the fixed plan costs as the input grows #

At eight elements the price of not adapting is three comparisons over the floor. The question is how the price grows.

The network’s line pulls away from the other two steadily, and the ratio in the caption climbs by close to half a unit every time the input quadruples. That is the signature of an extra logarithmic factor. Merge sort’s worst case is $n\log_2 n - n + 1$ at a power of two; Batcher’s network has $(k^2 - k + 4)\,2^{k-2} - 1$ comparators on $n = 2^k$ positions, which grows like $\tfrac{1}{4} n \log_2^2 n$. The ratio therefore grows like $\tfrac{1}{4}\log_2 n$, which is 4 at 65,536, and the plate’s 4.07 is that prediction plus the lower-order terms. The network’s depth, $k(k+1)/2$, is 136 at the same size.

So the class is different. Merge sort is $\Theta(n\log n)$ in comparisons; Batcher’s network is $\Theta(n\log^2 n)$, and no amount of fitting at small sizes would have been needed to find that out, since the count is a formula in $n$. What O-notation does not say warns that a class hides the constant, and here the constant — a quarter — is what keeps the extra factor under two until somewhere between 64 and 256 elements.

Two further facts bound what better networks could do, and it is worth being careful about which of them is settled. Networks with $O(n\log n)$ comparators exist: Ajtai, Komlós and Szemerédi constructed one in 1983, so the extra logarithm is not forced. But the constant in that construction is so large that by every published estimate it loses to Batcher’s network at any size anyone sorts. And at small sizes the best networks known beat Batcher’s by a little — for sixteen positions a network of 60 comparators has long been known, against Batcher’s 63 — while whether 60 can be beaten is, as far as the literature records, still open.

The count that still varies #

Several essays have insisted that “how many operations” has no answer until the operation is named, and the count somebody chose found that ranking ten sorts by six different counts gives six different orders. A network fixes its comparisons. It does not fix everything.

The exchanges have a distribution as wide as the network allows — anywhere from none, on sorted input, to all nineteen comparators exchanging on exactly one ordering of the 40,320. Only the comparisons are fixed.

Reversed input is not that ordering. It needs twelve exchanges, not nineteen, because Batcher’s first round pairs neighbours and exchanges all four pairs of a reversed array at once, after which the array is no longer reversed and later comparators find much of their work done. The one ordering that makes every comparator exchange is one on which each comparator’s two positions happen to arrive out of order every time, which is a property of the network and of that ordering together, and has nothing to do with how disordered the ordering looks.

Merge sort, as implemented here, is the mirror image. Every merge copies both of its runs back into place whatever their contents, so merge sort writes $n\log_2 n$ elements on every ordering — 24 at eight — while its comparisons vary from 12 to 17. One run, four counts, four answers made the general point that a sort’s ranking depends on the count chosen; this pair makes a sharper one. “This sort’s cost does not depend on its input” is not a property of a sort. It is a property of a sort and a count together, and the two sorts on this plate each have one count that is flat and one that is not, and they are different counts.

The distinction matters most where the flat count is the reason for using the algorithm. Cryptographic code that must sort secret data is required not to let the pattern of its work reveal the data, because the time a program takes and the memory it touches can be observed. A network’s comparisons are already fixed. Its exchanges are not — a conditional swap is exactly the kind of data-dependent work that leaks — so a constant-time implementation writes every comparator as an unconditional pair of writes, the smaller value to one position and the larger to the other, which makes the writes 38 on every ordering of eight and removes the last distribution. Merge sort’s comparisons, by contrast, cannot be flattened without turning it into something else, because which element it takes next is the answer to a comparison.

Nothing for an adversary to answer #

Two essays before this one searched for expensive inputs. The worst case found by climbing swapped positions in search of a higher count, and it pointed McIlroy’s adversary, which answers each comparison so as to make the sort’s next choice a bad one, at five sorts. Against first-element quicksort the adversary built an input costing $n(n-1)/2$; against median-of-three quicksort, half of that.

Pointed at a network, both searches find nothing, and not because they fail. The climb’s landscape is flat: every swap leaves the comparison count exactly where it was, so a climb that keeps swaps that do not lower the count wanders at random and a climb that keeps only rises never moves. The adversary’s answers change which elements end up where, and cannot change which comparison comes next, because nothing in the network consults them. The depth limit that almost never fires described the defence a library sort builds against an input decided while the sort runs — a counter and a fallback. A network needs no defence, because there is no decision for the input to influence. Every input is the worst case, and every input is also the best.

That is the precise sense in which a network is robust, and it costs exactly what the count plate shows: the questions a network asks have to be enough for the worst input, and it asks them of every input.

Checked on 65,536 inputs instead of twenty trillion #

Fixing the plan has one more consequence, and it is the one that most changes what can be known about the algorithm.

The count over every input stopped at eight elements because an adaptive sort’s behaviour on one ordering says nothing about its behaviour on another, so certifying that it sorts every input of sixteen means running it on all $16! \approx 2.09 \times 10^{13}$ of them. A network can be certified on far fewer. The zero–one principle says that a comparator network sorts every input if and only if it sorts every input made only of zeros and ones. The argument is short. A comparator puts the smaller value first; if every value is first passed through any order-preserving function, the comparator still puts the smaller value first, so the network and the function commute. Suppose some input came out unsorted, with a larger value $a$ ahead of a smaller $b$. Map every value below $a$ to zero and every value from $a$ up to one: the network run on that zero–one input produces the mapped output, which has a one ahead of a zero, and so is unsorted too. A failure on any input implies a failure on a zero–one input.

The argument uses the fixed plan at the step where the network and the function commute. An adaptive sort’s next comparison depends on answers that the mapping changes — two elements that differ can map to equal zeros — so it follows a different path on the mapped input and the principle does not apply to it.

The whole network passes: 65,536 inputs, each carried through 63 comparators, a check that takes a fraction of a second. It is a complete proof that this network sorts every input of sixteen, of any values, and it was obtained by running the network rather than by reasoning about it.

The bars are the half of the check that matters most, the part that shows it can reject. Every one of the 63 comparators is needed: remove any one and at least 64 of the zero–one inputs come out unsorted, so no comparator in Batcher’s network on sixteen positions is spare. That is not a claim that 63 is the fewest possible, and it is not one — the 60-comparator network is a different network, not this one with three removed — but it does say that Batcher’s network cannot be improved by deleting anything. Both halves are tested: the full network must sort every zero–one input, and a network missing its last comparator must be refused by the same check. The check must reject is the standard both are held to.

The bars also say which comparators are load-bearing, and it is not the ones a reader of the drawing would guess. The seven comparators of the last round, which fix up neighbours after everything else, protect between 64 and 6,400 inputs each. Four comparators earlier in the final merge protect more than 26,000 each, and two of them 44,100 — two in every three of the zero–one inputs. A comparator’s importance is not uniform, and the zero–one check measures it exactly.

What a fixed plan is for #

Three uses follow from the measurements, and each can be read off a plate.

Small inputs. At sixteen elements the network costs 1.29 times merge sort’s worst case, and at eight it beats heapsort and median-of-three quicksort on every input. For a base case that is sorted millions of times inside a larger algorithm, a count that never varies and a loop with no branches can be worth more than a few comparisons.

Parallel hardware. The network on 65,536 positions needs 136 rounds. An adaptive sort’s comparisons cannot be scheduled into rounds at all without first being run, and a machine with many simple processing lanes runs a network round in one step.

Work that must not depend on its data. Constant-time code needs every counted quantity flat, and a network written with unconditional exchanges is the natural way to get there.

And one use it is not for: a single processor sorting a large array with no secrecy requirement, where the network’s extra logarithm — a factor of four at 65,536 and growing — is paid for nothing. How close anything gets to the floor ranks sorts by their distance from $\log_2 n!$; on that ranking Batcher’s network at 65,536 sits at 4.19 times the floor, further out than heapsort, and it gets further out as the input grows.

Still open: the count of the part that was read #

A network cannot adapt to its input, and every sort measured on this page can. Neither kind adapts to the caller. A sort computes the whole of an order — where every element belongs — and hands it back, and a great deal of real sorting is done by callers who read the first ten elements of the result and discard the rest: the top results of a search, the smallest distances, the first page of a listing.

For those callers every sort here is doing work nobody reads. Merge sort’s count on 65,536 elements is about a million comparisons whether the caller wants all of them in order or only the smallest ten. There are methods that pay for what is read — a heap built once and popped ten times, a partition that isolates the smallest ten and sorts only those, a quicksort that stops recursing into parts nobody has asked for yet — and their counts depend on a quantity no sort’s count mentions, the number of elements the caller will take. How the counts compare as that number runs from one to all of them, and what the least any method can pay for the first $k$ is, is the next measurement.