Interactive sorting network diagram with step-by-step animation
A sorting network is a fixed-structure comparator network that sorts any input sequence using a predetermined arrangement of compare-and-swap operations. Unlike adaptive algorithms such as quicksort or mergesort, a sorting network performs exactly the same comparisons regardless of input data.
Each comparator connects two wires (positions i and j) and routes the smaller value to the upper wire and the larger value to the lower wire. If the values are already in order, nothing changes; if not, they are swapped. This is the fundamental compare-and-swap operation.
The depth of a sorting network is the maximum number of layers from input to output. Comparators at the same depth have no data dependencies and can execute simultaneously in parallel. Networks with smaller depth sort faster. The theoretical optimal depth for N elements is O(log N).
Traditional sorting algorithms (like quicksort) decide the next comparison based on previous results, so the comparison order depends on the input. Sorting networks predetermine all comparisons, making them ideal for hardware implementation and GPU parallel computing, but unable to optimize based on input characteristics.
Sorting networks are widely used in: GPU sorting (bitonic sort is the foundation of CUDA sorting), hardware sorting circuit design, oblivious sorting in secure computation, database query optimization, and network packet sorting. For small N (N <= 32), hand-optimized networks are often faster than general-purpose algorithms.
For small N, the known optimal comparator counts are: N=4 requires 5 comparators, N=5 needs 9, N=6 needs 12, N=7 needs 16, N=8 needs 19, N=9 needs 25, N=10 needs 29, N=16 needs 60. The 0-1 principle proves that verifying all 2^N binary inputs is sufficient to confirm network correctness.