Presets
Network and input
Or click any beam in the scene. A removed comparator is shown in red and stays level; the network then usually fails to sort.
Playback
Camera and display
Model checks
Checking...
The science
What a sorting network is
A comparator on wires i < j puts min(a,b) on wire i and max(a,b) on wire j. A network is a fixed list of comparators grouped in layers (comparators in one layer touch disjoint wires, so they can fire at the same time). Unlike quicksort nothing depends on the data, which is why networks are used in GPUs and hardware.
Networks in this yard
Bitonic (Batcher 1968): for n = 2m, depth m(m+1)/2 and (n/2)·m(m+1)/2 comparators. Odd-even merge sort (Batcher): same depth, (m2-m+4)·2m-2 - 1 comparators (19 for n = 8, 63 for n = 16). Odd-even transposition: n rounds of neighbour comparisons, n(n-1)/2 comparators. Bubble network: the comparisons of bubble sort scheduled as early as dependencies allow, depth 2n-3.
The 0-1 principle
If a comparator network sorts every input made of zeros and ones, it sorts every input. Reason: replacing every value x by [x ≥ t] commutes with a comparator (min and max are monotone), so a permutation that fails at some threshold t gives a failing 0-1 input. Checking all 2n bit patterns replaces checking n! permutations (65536 instead of 2×1013 for n = 16). The page tests this exhaustively, runs 20000 random permutations as an independent check, and for a faulty network lifts a failing 0-1 vector back to a real failing permutation.
Counting bounds
A sorting network needs at least ceil(log2 n!) comparators (information bound) and depth at least ceil(log2 n). For n = 8 the bound is 16 and the best known size is 19; for n = 16 the best known network has 60 comparators against Batcher's 63 (typical literature values, check before quoting).
The balance beam (physical metaphor)
One comparator is a beam of half-length L pivoted at its centre, with a pan hanging from each end. For tilt angle θ (positive when the high lane's end goes down):
I θ'' = (mj - mi) g L cosθ - M g h sinθ - c θ', with I = M L2/3 + (mi+mj) L2, beam mass M, centre of mass a height h below the pivot and damping c = 2ζ√(M g h I).
Equilibrium: tanθ* = (mj - mi) L / (M h). Small oscillation about the level beam has period T = 2π / (ω0√(1-ζ2)), ω02 = M g h / I. Both are checked against the integrated ODE. Stops at ±8 deg make the beam saturate, so any weight difference of one unit is decided clearly; a tie leaves the beam level.
The decision rule that moves the marbles is a > b on the values. The beam is a physical model alongside it: the page counts how often the sign of the tilt agrees with that rule.
Honest simplifications
Marble weight is m = (value) × (mass per value unit); the marble radius is only a visual cue. The 1 unit = 4 cm scale, beam mass density, pivot height h and damping are illustrative design constants, not measured hardware. Pans are hung by rods that stay vertical, friction in the knife-edge is lumped into the damping term, and the swap motion (one marble hops over, the other passes underneath) is an animation, not a contact simulation. Comparators of one layer are staggered along the rails only so that their beams do not overlap on screen; in the algorithm they fire simultaneously.
What to try
- Run odd-even merge 8 and bitonic 8 on the same input: both take 6 layers, but 19 versus 24 comparators.
- Remove one comparator and press "Run all checks": the 0-1 test finds the exact fraction of binary inputs that fail.
- Choose "Already sorted" - nothing swaps, but all beams still weigh: the network never skips work.
- Compare "Reversed" with "Random" in the inversions graph: the network removes a similar share of disorder per layer regardless.
- Use "Many duplicates": equal weights leave the beam level and the marbles are not exchanged.