Bitonic Sorting Network

Bitonic Sequences and Data-Oblivious Networks

A sequence is bitonic if it monotonically increases and then monotonically decreases (or can be circularly shifted to do so). Unlike data-dependent branching algorithms such as Quicksort, a bitonic network executes the exact same wire comparisons in every run, eliminating branch divergence across parallel lanes.

Comparator Schedule and Depth Complexity

For N = 2³ = 8 wires indexed 0..7, outer merge block sizes run over k = 2, 4, 8 and inner strides run over j = k/2, k/4, ..., 1. Within each layer, wire i compares with i XOR j (when (i XOR j) > i), sorting ascending when (i AND k) = 0 and descending otherwise. Each layer contains N/2 = 4 disjoint comparators, yielding log₂(N) · (log₂(N) + 1) / 2 = 6 parallel layers and 6 · 4 = 24 comparators.

Worked Example

Trace the 8-wire input [3, -1, 4, -2, 0, 2, -3, 1] through the 6 bitonic stages:

1. Layer 1 (k = 2, j = 1): Pairs (0,1) and (4,5) sort ascending; pairs (2,3) and (6,7) sort descending, producing [-1, 3, 4, -2, 0, 2, 1, -3].
2. Layers 2 and 3 (k = 4, j = 2 then 1): Merge the first four wires ascending into [-2, -1, 3, 4] and the last four wires descending into [2, 1, 0, -3], forming one length-8 bitonic sequence.
3. Layers 4, 5, and 6 (k = 8, j = 4, 2, 1): Perform a full ascending bitonic merge across all 8 wires, finishing with [-3, -2, -1, 0, 1, 2, 3, 4], 6 completed layers, 24 comparators, and 0 inversions.

Experiment

Inspect layer-by-layer compare-exchange operations in https://riano.app/module/bitonic-sorting-network:

1. 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.
2. Click Finish to complete all 6 stages and confirm 24 completed comparators and 0 inversions.
3. 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.

Limitations

Standard bitonic sorting networks require N to be a power of 2 and perform O(N log² N) total comparisons, which is asymptotically more total work on a single sequential CPU core than O(N log N) comparison sorts such as Merge Sort.

Common Pitfalls

Expecting inversions to decrease monotonically after every single layer is a common misconception: because stages 1..3 intentionally sort the second half of a block in descending order to construct a bitonic sequence, intermediate layers can temporarily increase the global inversion count before the final merge stage eliminates all inversions.

References

The parallel comparator schedule and GPU sorting architecture follow classic parallel computing literature:

• GPU Gems 2, Chapter 46: Improved GPU Sorting (Bitonic Merge Sort)