Zero-One — workshop

A sorting network has no branches, so you cannot argue with it — you can only test it, and testing it properly means all n! orderings. The 0-1 principle collapses that to 2^n, drawn here as every binary input at once, banded by weight, failures in red. Pull one comparator out of bitonic and exactly one cell in 256 turns — which is also 576 of the 40,320 permutations, because a binary counterexample is never one input, it is a class.

A sorting network is a fixed list of compare-exchange operations. Wire a against wire b: afterwards the smaller value is on a and the larger on b. That is the entire instruction set, and the list never changes — no branches, no loop counters, no data-dependent anything. The same comparators fire in the same order whether you hand it a sorted array or its reverse, which is exactly why you can etch one into silicon, unroll it across SIMD lanes, or run every comparator in a layer at once.

The bill for that rigidity comes due when you ask whether it works. There is no invariant to carry through a loop, because there is no loop. All you can do is run inputs through it. And “all inputs” means every ordering of n distinct values: 40,320 at eight wires, and twenty-one trillion at sixteen.

The 0-1 principle says you do not have to. A comparator network that sorts every 0-1 vector sorts every input, of every type. Eight wires: 256 cases. That is not a sample and it is not a heuristic, it is the whole proof, and it runs before your finger leaves the mouse button.

So the piece draws those 256 cases. Every binary input is a cell, banded by how many ones it has — one all-zeros case at the top, 70 balanced ones through the middle, one all-ones case at the bottom, which is why the sweep is shaped like the binomial coefficients it is made of. Grey passes. Red does not.

Five networks and one that is one short

odd-even merge — Batcher’s. 19 comparators, depth 6, and size-optimal for eight wires. Every comparator points the same way.
bitonic — 24 comparators, also depth 6. Half its comparators point upward, because it builds bitonic sequences and folds them; the downward arrows in the drawing are the algorithm, not a bug.
transposition — bubble sort with every independent swap done at once. 28 comparators, depth exactly 8. The easiest network to believe, because each row is one pass of a sort you already accept.
insertion — the same 28 comparators arranged as a staircase, depth 13. Same size, twice the latency: the picture of why depth and size are separate costs.
one short — bitonic with a single comparator lifted out.
blank — nothing, so you can build one yourself.

One short is the point of the whole thing. Of the 24 ways to remove a single comparator from bitonic, exactly one leaves a network that fails just one of the 256 binary inputs: 11110000. Every other removal breaks between 8 and 225 of them. So this is the gentlest possible damage to a sorting network, and the sweep still finds it instantly, as one red cell in a field of grey.

What a red cell is worth

Press lift it. The failing vector 11110000 becomes a permutation of 1…8 — the four zeros get four distinct low values in any order, the four ones get the four high values — and the network makes the identical comparisons and lands in the identical wrong place. That is the mechanism behind the principle: comparators commute with every monotone function, so thresholding a real input reproduces its binary run exactly. Running it backward, a binary counterexample is not an anecdote, it is a class: 11110000 stands for 4!·4! = 576 of the 40,320 permutations, and the readout counts them.

Which produces the fact this piece exists to show, and it is the opposite of the one you expect. Random testing is not blind here — it cannot be. A broken n-wire network fails at least ⌊n/2⌋!·⌈n/2⌉! of the n! orderings, because failure always arrives in whole lift classes, so even the subtlest possible bug in an eight-wire network fires on one input in seventy. Throw two thousand random arrays at one short and roughly thirty of them come back wrong.

So random testing will tell you that something is broken. What it will never do is tell you nothing is — 40,320 is not a suite you run, and 16! is not a number you run anything over. The 256-case sweep answers the question random testing structurally cannot answer, in less time than it takes to draw the answer.

Building one

Drag between two wires to add a comparator; the wire you start on keeps the minimum, so dragging upward builds a descending comparator and you can draw bitonic by hand. Click a comparator to remove it. Where you drop it along the wire decides where it lands in the sequence, not just where it renders. The sweep re-runs on every edit, so the honest way to use this is to delete the six-layer network, build something you think sorts, and watch the grid tell you.

Switch to 16 wires and the two numbers separate for good: 65,536 binary cases against 20,922,789,888,000 orderings. The sweep still runs in about thirty milliseconds. There is exactly one removal from the 80-comparator bitonic network that leaves a single failing case, and it is in there — one red pixel out of 65,536, which is a picture of what exhaustive means.

Reuse

src/zero-one.js is a framework-free ES module, no rendering and no timers:

bitonic(n), oddEvenMerge(n), oddEvenTransposition(n), insertion(n), tampered(n) — comparator lists as directed [min, max] wire pairs. buildNetwork(kind, n) dispatches by name.
layersOf(net, n) / depthOf(net, n) — greedy layering: a comparator sits in the first layer after the last one that touched either of its wires.
runNetwork(values, net) — one frame per layer (frame 0 is the input), each carrying the vector and which comparators actually swapped, so a renderer can scrub in either direction. Same trace-per-tick shape as staircase and sift.
sweepZeroOne(net, n) — all 2^n binary inputs, returning a pass bitmap and the failing masks.
lift(bits, rng) — a failing 0-1 vector as distinct values that fail the same way. liftClassSize(mask, n) is how many such inputs exist.
exactPermutationFailures(net, n) — every n! ordering, for checking the claim above rather than believing it. Tractable to n = 8 on purpose.

scripts/analyse.mjs regenerates every number quoted here; re-run it after touching the module.

Gotchas

Comparators are directed. [a, b] puts the minimum on a, so [5, 2] is a descending comparator and bitonic is full of them. A renderer that assumes a < b draws bitonic wrong and still shows it sorting, which is the worst kind of wrong.
The depth shown is from greedy layering, which is optimal for this scheduling problem but is not the minimum depth over all networks of that size — depth 6 is optimal for 8 wires, and the blank canvas will happily let you build worse.
exactPermutationFailures is factorial and deliberately ungated: at n = 16 the demo does not call it, and neither should you.
Order is part of the network, not a presentation detail. The same multiset of comparators in a different sequence is a different network and sweeps differently, which is why the edit drop position has to mean something.
The demo bundles its own copy of zero-one.js (self-contained by contract); re-copy after editing src/.