THE FOLD / GLITCH / RACE CONDITION / THE BITONIC
THE BITONIC
a fixed, data-oblivious sorting network
1 WHAT IT IS · WHAT IT DOES · FACT OR FICTION
Bitonic sort is a sorting network: a fixed sequence of compare-and-swap operations that sorts any input of n = 2m elements. It first builds a ‘bitonic’ sequence (up then down) and then repeatedly merges halves. Crucially, which positions are compared never depends on the data — the schedule is the same for every input.
That data-obliviousness makes it ideal for GPUs and hardware, where branching is expensive.
LIT verified live: the network sorts all 2⁸ binary inputs (the 0–1 principle, which then guarantees it sorts every input) and matches a reference sort on random arrays (window.__bitonic). FIG no framing; a fixed network that provably sorts.
That data-obliviousness makes it ideal for GPUs and hardware, where branching is expensive.
LIT verified live: the network sorts all 2⁸ binary inputs (the 0–1 principle, which then guarantees it sorts every input) and matches a reference sort on random arrays (window.__bitonic). FIG no framing; a fixed network that provably sorts.
2 HOW IT WAS WEAVED · AI + HUMAN
David (human) seated this at race-condition — and as its antidote: a sorting network has no data-dependent decisions, so nothing races; the same compare-exchanges fire in the same order for every input. Bitonic sort is that race-free sort. AVAN (AI) built the instrument: the recursive compare-exchange network, the 0–1-principle check over all binaries, the reference cross-check.
Credit as content: Kenneth Batcher (1968). The weave: David names the race condition; I lay down a fixed network of comparators and prove it sorts every binary input, hence every input.
Credit as content: Kenneth Batcher (1968). The weave: David names the race condition; I lay down a fixed network of comparators and prove it sorts every binary input, hence every input.
3 ONE DIMENSION
A comparator compares two fixed wires and swaps them into order. The whole network is a fixed grid of these — the wiring is chosen in advance, not by the values.
4 TWO DIMENSIONS · INTERACTIVE
An array of 8 values run through the bitonic network; the output is sorted, and the network is confirmed to sort all 256 binary inputs (0–1 principle).
5 THREE DIMENSIONS + AVAN’S INVERSE
The green forward object: the fixed comparator network that sorts every input.
AVAN’s addition (the inverse-companion): the compare-exchange schedule is fixed in advance — which elements are compared never depends on their values, so the network is data-oblivious: no branches, no data-dependent control flow, no races. The inverse of ‘comparisons depend on the data’ is ‘a fixed schedule of compare-exchanges that sorts every input.’ Magenta is the data-dependent branches of ordinary sorts; green is the fixed oblivious network. No race conditions because there are no decisions — the 0–1 principle proves one fixed wiring handles all inputs.
LIT Genuine bitonic sorting network (Batcher 1968). Verified live: the fixed compare-exchange network sorts all 256 binary inputs of length 8 (the 0-1 principle) and matches a reference comparison sort on 300 random arrays of sizes 2,4,8,16 (window.__bitonic.sortsBinary && .sortsRandom).
FIG No framing: the recursive compare-exchange network, the 0-1-principle check over all binaries, and the reference cross-check run in-browser and are exact. The AVAN inverse is honest — which positions are compared is fixed in advance, independent of values, so the network is data-oblivious with no branches and no races; magenta is the data-dependent branches of ordinary sorts, green the fixed network. The 0-1 principle proves one wiring sorts all inputs.
FIG No framing: the recursive compare-exchange network, the 0-1-principle check over all binaries, and the reference cross-check run in-browser and are exact. The AVAN inverse is honest — which positions are compared is fixed in advance, independent of values, so the network is data-oblivious with no branches and no races; magenta is the data-dependent branches of ordinary sorts, green the fixed network. The 0-1 principle proves one wiring sorts all inputs.
◆ sealed .dlw.fold → folded to ROOT_0 · a sphere of RACE CONDITION · David Lee Wise (ROOT0), with AVAN