Bitonic Sort

Build bitonic sequences and merge them through a fixed comparison network whose columns can run in parallel.

Core idea

A bitonic network first creates sequences that rise and then fall, then merges them with compare-exchange stages whose distances repeatedly halve. The comparator pattern depends only on positions, not values.

Read the visualization

Read the network from left to right. Comparators in one column are independent and can execute together; each highlighted pair is oriented toward the order required by its current bitonic block.

Arrange the input at the left edge of the fixed comparison network.

1function bitonicSort(a: number[]): void {
const n = a.length;                        // n  as  2 init
for (let k = 2; k <= n; k *= 2) {          //  phase: init length  k init
  for (let j = k >> 1; j >= 1; j >>= 1) {  //  one  column:  compare  distance  j(column column column parallel)
    for (let i = 0; i < n; i++) {
      const l = i ^ j;                     //  and  i  distance  j column
      if (l > i) {
        const asc = (i & k) === 0;         // column direction: column or column
        if (asc ? a[i] > a[l]: a[i] < a[l])
          [a[i], a[l]] = [a[l], a[i]];     //  compare  swap ( compare done)
      }
    }
  }
}
15}

n / column count8 / 6

parallel depthlog²n level = 6 pass

1 / 8

Complexity and tradeoffs

Time: O(n log^2 n). Space: O(1) auxiliary. The data-independent network suits parallel hardware and normally expects a power-of-two length.

Invariant: After a merge stage of size k, every completed k-position block has the required monotone order.

Where it fits

Data-independent comparisons make Bitonic Sort useful on sorting networks, SIMD hardware, and GPUs. Padding or a specialized network is needed when the input length is not a power of two.

Algorithm Visualizer

Bitonic Sort

Core idea

Read the visualization

Complexity and tradeoffs

Where it fits