A sort that never looks at the answers

An ordinary sorting routine is a conversation. It compares two items, and what it compares next depends on the result. Quicksort picks a pivot and partitions according to what it finds, and merge sort takes from whichever list has the smaller head. The record of comparisons depends on the data, and different inputs follow different paths.

A sorting network gives that up. It is a fixed list of comparators, each naming two positions and doing one thing: if the numbers there are out of order, exchange them. Nothing else ever happens. The list is written down before any number has arrived, and it is applied in the same order whatever the numbers are. It takes the strongest possible reading of the word oblivious: the sequence of positions touched reveals nothing about the data, because it was fixed in advance.

Whether such a list can sort everything looks as if it should be hopeless to decide, since $n$ wires have $n!$ orderings. It turns out to be surprisingly easy to check, and very hard to optimise. The study of it mixes the arithmetic of permutations with a piece of pure logic, and it has connections with the wiring diagrams in which the sign of a permutation was first read off.

The picture shows the classic presentation. Horizontal lines are wires carrying numbers from left to right, and each vertical bar is a comparator that sends the smaller of its two values to the upper wire. Comparators in the same vertical position can operate simultaneously, because they involve different wires, so the network’s depth, its number of stages, measures its speed in hardware. It was invented in part because hardware works that way, and it came back into use when graphics processors made thousands of parallel comparators cheap.

Noughts and ones are enough #

To verify a network by testing, it would seem that all $n!$ orderings must be tried. The 0–1 principle says that the $2^n$ strings of noughts and ones suffice, and at twelve wires that is the difference between 479 million tests and 4,096.

The proof is one of the prettiest arguments in the subject, and it fits in a paragraph. Let $f$ be any non-decreasing function on numbers. A comparator applied to $f(a), f(b)$ produces $f(\min(a, b)), f(\max(a, b))$, because $f$ preserves order. So running the network on $f$ applied to the input is the same as applying $f$ to the output of running it on the input. Now suppose the network fails to sort some input of arbitrary numbers: somewhere in its output a larger value $v$ stands above a smaller value $u$. Take $f$ to be the threshold function, 0 below $v$ and 1 from $v$ upward. Then the output on $f(\text{input})$ has a 1 above a 0, and $f(\text{input})$ is a string of noughts and ones that the network fails to sort. So a network that sorts all 0–1 strings sorts everything.

That principle is often attributed to Knuth, who recorded it in The Art of Computer Programming, crediting W. G. Bouricius. The two tests were checked against each other here: Batcher’s networks were tested on all orderings up to eight wires and on all 0–1 strings up to sixteen, and there were no disagreements.

A network can therefore be judged by following a single object: the set of 0–1 strings still possible after each comparator. It begins with all $2^n$ strings and it has to end at exactly the $n + 1$ strings that are in order. Each comparator can only reduce that set, by removing the strings with a 1 above a 0 at its two positions. The longest sorted run inside a permutation, which a sequence that cannot avoid a staircase studies, has nothing to do with this count: a network is judged on every input at once.

This makes visible what the comparators are doing. Under Batcher’s network the count goes 256, 192, 144, 128, 96, 80, 60, 45, 40, and it reaches 9 at the nineteenth comparator. Under bubble sort it goes 256, 192, 160, 144, 136, 132, 130, 129, because that network passes the largest number down the wires, and its later comparators in each pass act on a set that is already partly sorted in that respect. After seven comparators the merge network has 45 strings left and bubble sort has 129. The bubble network has nine more comparators still to spend after the merge network is finished.

Four wires in full #

Before the numbers get large, the smallest interesting network is worth following by hand, since every feature of the larger ones is already there. Four wires need five comparators. Two of them act first, on wires 1 and 2 and on wires 3 and 4, and they could run at the same moment. Now each pair has a known smaller and a known larger. Two more comparators follow, one between the two smaller values and one between the two larger. The first sends the overall minimum to wire 1, and the second sends the overall maximum to wire 4. That settles the ends. The fifth comparator handles the two middle wires, which hold the two values that have lost or won exactly once and whose order is still unknown.

The 0–1 reading of the same network makes the economy clearer. Of the sixteen strings, the first stage removes those with a 1 above a 0 in either pair, leaving nine. The second stage leaves six, and the last leaves five, the five strings that are in order. An adaptive sort would also need five comparisons in the worst case for four items, so at this size nothing has been lost by writing the list in advance. That equality does not last: at five items an adaptive sort needs seven comparisons in the worst case and a network needs nine.

There is one thing that this small example hides. A comparator is allowed to send the smaller value to the lower wire instead of the upper. It might seem that mixed directions give extra power. They do not: Knuth’s untangling argument shows that any network with mixed directions can be redrawn, by swapping the names of wires from a given point onward, as a network with all comparators pointing the same way. The swap of names is a permutation applied to the rest of the diagram, the same bookkeeping that the sign of a shuffle uses when it composes rearrangements, and it is what justifies treating any two sets of strings that differ by a renaming of wires as a single position in the searches below. And a network can contain a comparator that never does anything, on every input, in which case it is simply redundant. None of the shortest networks has one, and a test for redundancy can be read off the list of reachable strings.

How few comparators #

The obvious lower bound comes from counting. A network that sorts all orderings must distinguish all $n!$ of them, and each comparator gives at most one bit, so $\log_2 n!$ comparators are needed, the same bound as for any comparison sort. For small $n$, the known minimum sizes are listed in the figure.

The least sizes through eleven wires are 1, 3, 5, 9, 12, 16, 19, 25, 29 and 35. For four wires the counting bound of 5 is attained, and at five wires the bound of 7 is not: nine are necessary. The gap between $\log_2 n!$ and the truth is the first thing the figure shows that an adaptive sort does not have, because an adaptive sort can always use its comparison to split the remaining possibilities almost evenly. A network must fix its comparator regardless. So the network’s next comparator has to work across every string that might have arrived there, and some will not be helped.

Finding these numbers has been a long project. Robert Floyd and Donald Knuth settled sizes up to eight wires by the 1970s through a mixture of clever constructions and hand reductions. The nine-wire value of 25 was proved only in 2014, by Michael Codish, Luís Cruz-Filipe, Michael Frank and Peter Schneider-Kamp, using a generate-and-prune search and a satisfiability solver; that case needs comparisons over a set of positions so large that it took years of computing in the first attempt. Jannis Harder took it to eleven and twelve wires in 2019. So after six decades, the exact answer is known for twelve values of $n$ and for no others.

The basic method fits in a page, for small cases. Treat each position in the search as a set of reachable 0–1 strings, since any two networks that reach the same set are interchangeable from then on. Two sets that differ only by renaming the wires are interchangeable too. So take the set of all strings, apply every comparator in turn, keep one representative of each resulting set up to renaming, and repeat, counting the levels. The search here at five wires holds 1, 1, 3, 8, 19, 26, 29, 19, 10 and 5 positions at successive levels, and the first level at which any set has just six strings is level nine. There is the proof. The same method finds 5 for four wires and 3 for three. The first six levels show the characteristic growth that makes this method explode at larger sizes: the positions at seven wires are already in the millions, and subsumption tests, in which one set is shown to be no worse than another, are what makes it barely possible at nine.

Halving and merging #

Asymptotically, the question is settled up to a factor, and a good practical network comes from one idea of Kenneth Batcher’s, from 1968. To merge two sorted lists, merge their odd-numbered items and their even-numbered items separately, and then compare neighbouring results once. Each of those merges works by the same rule. The 0–1 principle gives the short proof: a sorted list of noughts and ones is determined by how many noughts it has, and after the two half-merges the number of noughts in the odd and even result differ by at most two, so a final row of comparators finishes the job.

Its size is close to $\tfrac12 n \log_2^2 n$, and it is optimal at sizes up to eight, with 19 comparators at eight wires. From nine wires on it is not optimal: 28 against 25, 32 against 29, 38 against 35. The discrepancy grows, since the true minimum is of order $n \log n$ with a very large constant. But for a long way out, Batcher’s network is simply the best anyone actually uses.

Its depth is $k(k + 1)/2$ on $2^k$ wires, tested here from two wires to a thousand and twenty-four. It is squared in $k$, against a floor of $k$, and whether the square was necessary stood as a major open question until 1983. Miklós Ajtai, János Komlós and Endre Szemerédi then proved that a sorting network of depth proportional to $\log n$ exists, using expander graphs. It is one of the most striking theorems in the subject and no use whatsoever in practice. The constant, after Michael Paterson’s simplifications, is measured in thousands, and the smallest size at which the AKS network would be shallower than Batcher’s has a number of wires well beyond what any machine could contain. For parallel sorting in the real world, the logarithm squared wins, and its proof fits on an envelope.

Neighbours only, and the parity count #

Add one restriction and everything changes. Suppose every comparator must join neighbouring wires, as in bubble sort. This is the restriction under which the tokens of a puzzle move along the edges of a line. A swap then exchanges two adjacent items, the same elementary step as the transpositions counted in the crossings of a wiring diagram. The parity of a permutation changes by one with each. Now a comparator can remove at most one inversion, a pair of values standing in the wrong order, and it can remove one only when the two adjacent values involved are out of order.

So the row that is entirely reversed, $n, n - 1, \dots, 1$, has every one of the $n(n - 1)/2$ pairs inverted, and each comparator must remove exactly one of them. That many comparators are therefore necessary, and bubble sort, which uses exactly that many, is optimal among networks of neighbours. The figure’s staircase falls by exactly one at each of the 28 steps.

This is the count from the sliding tray, used differently. In a second empty square parity is a barrier: a single tile exchange changes the sign, and the sign of the arrangement decides what can be reached. Here no barrier applies, since a comparator is not obliged to act, and a network can leave any input unchanged. But the same integer, the number of inversions, is now a progress measure instead of a sign. The whole count, not only its remainder modulo two, is what bubble sort is paying for.

And there is a theorem that makes this restricted case far simpler than the general one. N. G. de Bruijn proved in 1974 that a network of adjacent comparators sorts every input if and only if it sorts the single reversed row. So one test replaces $2^n$. The test was run here against the full 0–1 test on two hundred randomly generated neighbour networks on six wires, and agreed on all of them, though most of those networks do not sort. The reason, informally, is that a neighbour comparator acts on the weak order of permutations, the same object a walk that changes one thing at a time moves on, and in that order the reversed row is the top element. Anything that brings the top down to the bottom must bring everything else down too. For general networks no such test exists, and it is known to be hard to decide: checking a sorting network is co-NP-complete, in contrast to the single test for neighbours.

Where they turn up #

Their fixed pattern gives networks some unusual uses. Because the sequence of memory accesses does not depend on the data, a sorting network leaks nothing about its input through timing or cache behaviour, a fact that matters in cryptographic software and in the oblivious computation of secret data. Because it has no branches, it suits a processor where branch mispredictions are the main cost. A short network for sixteen elements has fallen into wide use in graphics shaders and in the standard libraries of languages for sorting small runs. The minimum-size searches that seemed like pure puzzles turned out to have small commercial payoffs.

There is also a relation to the logic of circuits. A comparator on 0–1 values is just the pair of gates AND and OR. A sorting network on bits is therefore a monotone circuit computing every threshold function at once, one per output wire. So the AKS theorem provides monotone circuits of logarithmic depth for the majority function, and this result is used in lower-bound arguments in complexity theory, including those about formulas that cannot share a subcomputation. It is another case in which an impractical construction is good for proofs.

What the computations cover #

The search for least size was run through five wires with the method described, and it reproduces the published values 3, 5 and 9. Everything beyond that in the least-size table is quoted, from the sources named. Batcher’s network was checked on every 0–1 string to sixteen wires and on every ordering to eight, and its depth formula was checked up to 1,024 wires. Values shown for 2,048 and 4,096 wires are the formula, not a construction. De Bruijn’s theorem was tested on two hundred random networks and proved nowhere here.

The statements about AKS are cited. So are those about the hardness of verification and about practical use of small networks in libraries, and the claims about the size at which the AKS network would first beat the merge are orders of magnitude rather than careful calculations. The reachable-string counts have been computed exactly. They bear on the efficiency of a network only indirectly, since a set can be small without being close to sorted.

Still open: the sizes and the depths #

What is the minimum size for thirteen wires? The best known network has 45 comparators, and whether that is optimal is not known; beyond twelve wires only bounds exist. For depth the state of the art is a little further on: Daniel Bundala and Jakub Závodný showed in 2014 that the optimal depth for 11 through 16 wires is 8, 8, 9, 9, 9, 9, but beyond 16 only bounds exist. The asymptotic size is another matter: even with the AKS construction, no one knows whether the true least size at large $n$ approaches $n\log_2 n$ with a constant close to 1, or whether something inherent in being fixed in advance costs a substantially larger constant. It is a question that the counting bound cannot address and that nobody has a good tool for.

Then there is the simplest-sounding practical question of all. Is there a simple, explicit sorting network of depth $O(\log n)$ with a small constant? Expander-based networks exist, and Michael Goodrich’s zig-zag sort of 2014 is a simple deterministic design with $O(n \log n)$ comparators, though its depth is far from logarithmic. A network that is shallow, explicit and has a usable constant is unknown.

Half of what a comparison knows #

A network that fixes its comparisons in advance can be tested on $2^n$ strings of noughts and ones in place of $n!$ orderings, because a threshold applied to the input threads through every comparator. With neighbours only, one test, the reversed row, is enough, and the number of its inversions is exactly the size of the best such network. In general, the comparators cannot depend on the answers, and that costs real comparators, with least sizes growing past the counting bound from five wires onward and proven optimal to only twelve.

In the family of questions about wires and crossings, the sign of a permutation is the coarse invariant: it says what cannot be reached at all. The number of inversions is the finer measure, the actual distance to be covered when only neighbours can exchange. A sorting network that is free to reach across the wires can use far fewer steps, and how many fewer is a question that exhaustive search has answered to twelve wires and no theorem has answered beyond.