Sorting Network Wiring Diagram

The same networks as the 3D balance yard, seen from above as a classic wiring diagram. Slice the input at a threshold to see why checking 0-1 inputs is enough, and watch the set of possible states collapse layer by layer.

Switch to 3D
Presets
Network and input

Or click a comparator in the diagram. A removed comparator is drawn in red and does nothing.

Playback
Threshold slice (0-1 principle)

A comparator commutes with "x ≥ t", so the 0-1 pattern evolves exactly like the thresholded marbles.

Model checks

Checking...

The science

Wiring diagram

Each horizontal line is a wire carrying one value. A vertical bar between wires i < j is a comparator: the smaller value leaves on wire i, the larger on wire j. Bars in the same column act at the same time (they touch different wires); nested or overlapping bars are shifted sideways only so they stay readable.

Networks

Bitonic merge sort and Batcher's odd-even merge sort need n = 2m wires and depth m(m+1)/2. Bitonic uses (n/2)·m(m+1)/2 comparators; odd-even merge uses (m2-m+4)·2m-2 - 1 (19 for n = 8, 63 for n = 16). Odd-even transposition sort uses n rounds and n(n-1)/2 comparators; the bubble network has the same count but depth 2n-3.

0-1 principle and threshold slicing

For any threshold t let x → [x ≥ t]. Because min and max are monotone, net(thr_t(x)) = thr_t(net(x)). So a network that fails on a permutation also fails on one of its n - 1 threshold images; if every 0-1 input is sorted, every permutation is. The map below plots every 2n binary input as a pixel (green = sorted by the network, red = not); the white marks are the threshold images of the current marbles.

State-space collapse

Start with all 2n 0-1 vectors. A layer of c disjoint comparators maps the four patterns on each pair to three (00, 01, 11), so after the first layer exactly 3c·2n-2c vectors remain (checked on this page). A correct network ends with exactly n + 1 vectors, the sorted ones; a faulty one ends with more.

Counting bounds

At least ceil(log2 n!) comparators and depth at least ceil(log2 n) are needed. The best known sizes for n = 4..8 are 5, 9, 12, 16, 19 and for n = 16 it is 60 (typical literature values - verify before quoting).

Balance-beam model

The weighing beam is the same ODE as in the 3D page, Iθ'' = (mj-mi) g L cosθ - M g h sinθ - cθ'; its static tilt tanθ* = (mj-mi)L/(Mh) and small-oscillation period are verified by the checks, but the plan view only shows which end is heavier.

Honest simplifications

Marble mass = value × mass unit; sprite size is a visual cue only. Constants of the beam (mass density, pivot height, damping) are illustrative. The decision that moves the marbles is the exact comparison a > b.

What to try
  • Drag the threshold slider: the 0/1 badges show how a single threshold sorts like a smaller 0-1 problem.
  • Remove one comparator and find the red cells in the input map: those are the 0-1 inputs the faulty network cannot sort.
  • Compare "Odd-even merge 8" with "Bitonic 8": same depth, fewer comparators, and see the collapse curves.
  • Select the bubble network: depth 2n-3 but the state space collapses only slowly.
Loading...
State-space collapse: distinct 0-1 vectors after each layer (log scale)
Map of all 2^n binary inputs: green sorted, red unsorted, white = thresholds of the current marbles
Made with 🟠 Blender