Bitonic Sorting Network
Send eight values through a fixed parallel comparator network and inspect each sorting layer.
Free theory articleSend eight values through a fixed parallel comparator network and inspect each sorting layer.
Concept & interpretation
Batcher's bitonic sorting network is a data-oblivious parallel sorting algorithm that sorts N = 8 wires using 6 synchronous comparator stages (24 compare-exchange units in total), making it ideal for SIMD hardware and GPU execution.
Experiment
Inspect layer-by-layer compare-exchange operations in https://riano.app/module/bitonic-sorting-network:
- Set the 8 wires to reverse order
[7, 6, 5, 4, 3, 2, 1, 0]and click Step once to verify that Layer 1 swaps only the two ascending pairs (0,1) and (4,5), yielding[6, 7, 5, 4, 2, 3, 1, 0]and reducing inversions from 28 to 26. - Click Finish to complete all 6 stages and confirm 24 completed comparators and 0 inversions.
- Set an already-sorted input
[-4, -3, -2, -1, 0, 1, 2, 3]and step through layers 1..3 to see how the upper half intentionally reverses into descending order before the final k = 8 merge restores ascending order.