THE SORTING NETWORK a fixed sequence of comparators that sorts ANY input — data-independent
A sorting network sorts using a fixed, pre-wired sequence of comparators — each a “compare two wires and swap if out of order” — and here is the strange part: the same comparators, in the same order, sort every possible input. The sequence does not branch on the data; it is oblivious. That makes networks perfect for hardware and parallelism (independent comparators run at once) and is the basis of Batcher’s bitonic sort. The optimal network for 4 wires uses 5 comparators; feed it [3,1,4,2] and it sorts to [1,2,3,4] — and feed it [4,3,2,1] and the identical wiring sorts that too.
THE TECHNIQUE a fixed comparator sequence sorts every input — data-independent
The demo runs the fixed 5-comparator 4-wire network on [3,1,4,2] — and shows the same network also sorts [4,3,2,1]: live demo
HISTORY & CREDIT Batcher 1968 · bitonic sort
“A sort must look at the data to decide what to do.” — a sorting network does not: a fixed comparator sequence sorts any input. cited
the comparator · compare two wires, swap if out of order — the only operation. the obliviousness · a fixed sequence sorts EVERY input — no data-dependent branching. 1968 · Batcher — bitonic sorting networks; the basis of parallel/hardware sort.
A pre-wired ladder of compare-swaps that orders any input without ever looking at it — sorting made oblivious. data-independent
RECOMMEND FOR I-13 the fixed network, on the compiler
On the canonical compiler, the fixed 4-wire network sorts [3,1,4,2], and the identical comparators also sort [4,3,2,1]:
$ i13 run or_sortingnetwork.i13 # fixed 5-comparator network
RUN OK · 480 step(s) · peak stack 6 · call depth 4
is_sorted = 1 -- [3,1,4,2] sorted
same_on_other = 1 -- the SAME network also sorts [4,3,2,1]
Recommend as a keeper shot — the batch’s data-independence bid. A sorting network is oblivious: the control flow does not depend on the data, so two mechanisms — a data-dependent sort and a fixed network — compute the same sorted output while differing on whether they branch. That looks keeper-shaped. The honest counter: obliviousness is a property of the control flow / resource profile (no branches, fixed depth — B40), not extra output-structure; the sorted output is bit-identical either way, so it is a costlier/differently-shaped twin, not a carried channel. My lean: NULL by B40. But data-independence is a genuinely distinct shape — worth the panel’s look.