Comparator Lab sorting networks · ALG 15.3
Build a comparator network that sorts n values. Values enter at the top and flow down the wires. Click a wire, then another wire to add a comparator. The arrow points to the wire that gets the larger value, as in the book's figures. Click a comparator to delete it. Comparators that can run at the same time share a layer, so the number of layers is the parallel time.
comparators 0 layers 0
sorts 0 of the 0 0/1 inputs
Why only 0/1 inputs? The zero-one principle (ALG 15, exercise): a comparator network sorts every input if and only if it sorts every sequence of 0s and 1s. So 2n tests are enough. When the network fails, the lab shows a 0/1 input it gets wrong (dark = 1).
Best possible (proven optimal):
The optimal size for n = 9 and 10 was only settled in 2014, by a computer search (Codish, Cruz-Filipe, Frank, Schneider-Kamp). Your personal bests are highlighted.