Sorting Networks Visualization | Bitonic & 0-1 Principle

The idea: a fixed list of compare-and-swaps

A sorting network sorts with a fixed list of comparators on wires. Each wire carries one value from left to right. A comparator joins two wires: it puts the smaller value on the upper wire and the larger value on the lower wire. That is the whole machine. There is no loop, no "if this then look over there": the list of comparators is the same for every input.

Left: one comparator between two wires; 7 on the top wire and 2 on the bottom wire go in, 2 on top and 7 below come out. Right: a 4-wire network of 5 comparators in 3 layers sorting 3 4 1 2 into 1 2 3 4; the comparators of each layer touch different wires. — A comparator is min on top, max below; a network is layers of comparators on different wires.

The page draws 8 wires, w0 at the top to w7 at the bottom. Values flow from in to out; a pair that is out of order swaps wires (orange), a pair already in order passes (green). At the end every value is green if the wires read in order from top to bottom (Demo: bitonic sort on 8 values).

Depth vs comparator count

Comparators that touch different wires do not depend on each other, so they can fire at the same time. The page groups them into layers (the shaded bands L1, L2, …). Two numbers describe a network:

size: the number of comparators, the total work;
depth: the number of layers, the time when every layer runs in parallel.

Network	n = 4	n = 8	n = 16	Depth for n
Odd-even transposition	6, depth 4	28, depth 8	120, depth 16	n
Bitonic sort	6, depth 3	24, depth 6	80, depth 10	log n (log n + 1) / 2
Odd-even merge sort	5, depth 3	19, depth 6	63, depth 10	log n (log n + 1) / 2

Odd-even transposition is bubble sort as a network: it only compares neighbours, so a value can move one wire per layer and needs n layers (Demo: odd-even transposition, depth 8). Batcher's two networks need O(log² n) layers. A sequential sort needs about n log n comparisons; these networks do a little more work (O(n log² n) comparators) in exchange for very short parallel time.

Bitonic sort

A bitonic sequence goes up then down (like 1 4 6 8 7 5 3 2). Batcher noticed that one layer of comparators at distance k/2, a half-cleaner, splits a bitonic block of k values into two halves where every value in the top half is at most every value in the bottom half, and both halves are bitonic again. Repeating at distances k/4, k/8, … sorts the block.

Merging the sorted runs 1 3 6 8 and 2 4 5 7 on 8 wires. Comparing each wire with its mirror gives 1 3 4 2 above 8 6 5 7, every top value smaller than every bottom value; distance 2 gives 1 2 4 3 5 6 8 7; distance 1 gives 1 2 3 4 5 6 7 8. — Merging two sorted 4s: compare mirrors, then half-cleaners at distance 2 and 1.

To merge two sorted runs, the classic version sorts one run up and the other down so together they are bitonic. This page uses the equivalent "flip" form: the first layer of each merge compares each wire with its mirror in the block (w0–w7, w1–w6, w2–w5, w3–w4), so every comparator points the same way. For 8 wires: sort pairs (1 layer), merge into 4s (2 layers), merge into 8 (3 layers): 6 layers of 4 comparators, 24 in all.

Odd-even merge sort

Batcher's other network merges two sorted runs by merging their even-position values and their odd-position values separately, then fixing the few neighbours that can still be out of order. It has the same depth as bitonic sort but skips comparators whose outcome is already known: 19 instead of 24 for 8 wires (Demo: odd-even merge sort, 19 comparators). Layers 3, 5 and 6 have only 2–3 comparators, so some wires idle there.

The same comparisons for every input

A comparison sort like quicksort chooses its next comparison from the results of earlier ones. A network does not: on already sorted input the bitonic network still fires all 24 comparators in 6 layers, it only makes 0 swaps (Demo: sorted input still fires all 24). That looks wasteful, but it is exactly what parallel hardware wants: the work and the time are known in advance and never depend on the data. It also leaks nothing about the data through timing, which matters for constant-time cryptographic code.

The 0-1 principle

How do you check that a network sorts? Trying every order of 8 values means 8! = 40,320 tests. The 0-1 principle (Knuth) says it is enough to try every input made of 0s and 1s: 2⁸ = 256 tests.

Why it holds: suppose a network gets some input wrong, leaving a larger value b above a smaller value a. Replace every value ≥ b by 1 and every other value by 0. A comparator only ever asks "which is smaller", and this replacement keeps that answer, so the 0s and 1s travel exactly the way the real values did, and the output has a 1 above a 0. So any failure on real values shows up as a failure on some 0-1 input.

Top row: real input 5 6 7 8 1 2 3 4 through the broken network gives 1 2 3 5 4 6 7 8, with 5 above 4, not sorted. Bottom row: the same input with values at least 5 replaced by 1 and the rest by 0, that is 1 1 1 1 0 0 0 0, gives 0 0 0 1 0 1 1 1, with a 1 above a 0, not sorted. Arrows show each value maps to its bit. — Thresholding at 5 turns a failing input into a failing 0-1 input with the same comparator outcomes.

The page runs all 256 inputs through the network and colours a 16 × 16 grid: row = the bits on w0–w3, column = the bits on w4–w7 (Demo: the 0-1 principle, 256 tests). Then it takes one comparator out of the bitonic network, w0–w7 in layer 4. Only one 0-1 input fails, 11110000, and only 576 of the 40,320 orderings, about 1 in 70. Random testing could easily pass it; the 0-1 test cannot (Demo: one missing comparator, 1 failure in 256).

Why GPUs and SIMD use them

One layer, one instruction pair. With the values in vector registers, a whole layer is one vector min and one vector max plus a shuffle to line up partners. SIMD sorts of 8–16 values (inside AVX-512 quicksort, for example) are sorting networks.
No branch divergence. On a GPU, threads in a warp run in lockstep; a data-dependent if makes some wait for others. In a network every thread does the same compare-exchange.
Regular memory access. Thread i of a bitonic layer always reads wire i and its partner i XOR d, so loads are predictable and coalesced. GPU libraries sort small blocks with bitonic networks and merge the blocks afterwards.

See also parallel hardware for SIMD lanes and GPU warps, and Comparison Sorting for the sequential sorts whose comparisons depend on the data.

What the page leaves out

The page fixes 8 wires; real networks are built for any power of two, and non-powers of two need padding or pruned networks. It leaves out the search for optimal networks (the best known for 8 wires uses 19 comparators and depth 6, the same as odd-even merge sort; for 16 wires the best known size is 60), the AKS network with O(log n) depth whose constants are too large to use, the vector shuffles that move values between lanes, and how GPU sorts merge sorted blocks that are larger than one network.