← all experiments

The Same Swaps Every Time

Experiment № 106 · October 31, 2026

A sorting network is a sort that never decides anything. Values ride along wires, and at each comparator the smaller of two wires goes on top. The comparators are fixed in advance, so the network does the same swaps-or-not on every input, and the ones in each column can all fire at once. Kenneth Batcher showed in 1968 how to wire one that sorts anything.

Network

Wires

Input

Break it

comparators— columns (parallel steps)— swaps so far— knocked out0
least any sort could need— output—

Every comparator, everywhere

// wire i is above wire j if w[i] > w[j]: swap(w[i], w[j]) // that's all

How this network is wired

smallestlargest

Nothing in the network looks at a value to decide what to do next, which is why the same wiring runs on GPUs and in constant-time crypto code. The 0–1 principle (Knuth credits W. G. Bouricius) says that if a network sorts every input made only of 0s and 1s, it sorts every input at all. So Test only has to try 2ⁿ inputs, and a broken network always has a 0–1 input that proves it.

Click a comparator to knock it out, then hit Test.

Click a comparator to knock it out · space pauses · S steps · N new input · T tests · H hides panels

Experiment № 106 · The story

The Same Swaps Every Time

Why I picked it

This collection already has quicksort and patience sorting, and both of them are made of decisions: look at a value, then choose where to go next. I wanted the opposite kind of sort, one where the whole plan is written down before any data arrives. Kenneth Batcher published two of them in 1968, in a conference paper called "Sorting networks and their applications": the bitonic sorter and the odd–even merge sorter. He was working on parallel hardware at Goodyear Aerospace, and a sort with no branches can be built directly in wire. The same property turns up in places he can't have pictured. GPUs sort with bitonic networks because thousands of threads can run the same comparator pattern in lockstep, and Daniel Bernstein's djbsort uses a network so that the time it takes reveals nothing about the secret data it is sorting.

What I enjoy about it

The picture is the program. There is no hidden state, only wires and the rungs between them, and you can see the structure of the method in the shape of the drawing: the bitonic network folds each block in half like a ruler, the odd–even merge saves comparators by skipping the ones that could never matter, and transposition is bubble sort pressed flat into a brick wall. With the shuffled input, the coloured threads cross in a tangle on the left and come out the right side as a smooth gradient, every time. My favourite part is the Break it panel. Knock out one rung and the network looks almost the same, but somewhere among the 65,536 inputs of sixteen 0s and 1s there is one it now gets wrong, and the test finds it and plays it for you. I like that a fact about every possible list of numbers can be checked by trying only the boring ones.

Something you might take away

Deciding less can make you faster. Batcher's networks do more comparisons than a good sequential sort (63 for sixteen values where 45 is the theoretical floor) but because nothing waits on an earlier answer, sixteen values are sorted in 10 parallel steps instead of 45 in a row. And when something has to work for every input, it is worth asking whether a much smaller set of test cases stands in for all of them, the way 0s and 1s do here.