Bitonic Sort: Mechanism, Complexity Analysis & Interactive Visualizer

Bitonic Sort

A parallel comparison network sort: recursively builds bitonic sequences (first increasing, then decreasing) before merging them in parallel steps, optimized for GPU and hardware layouts.

How it works

Bitonic Sort, designed by Ken Batcher in 1968, is a comparison-based sorting network. A sequence is *bitonic* if it increases and then decreases, or vice-versa. Bitonic Sort operates by converting arbitrary inputs into bitonic sequences, then sorting them in parallel stages:

1. Bitonic Preparation: Recursively sort the left half ascending and the right half descending. This merges the two halves into a single bitonic sequence.
2. Bitonic Merger: Take a bitonic sequence of length \(k\). Compare each element in the first half with the corresponding element in the second half (index \(i\) vs. \(i + k/2\)). Swap them if they are in the wrong order. This step splits the array into two smaller bitonic halves.
3. Recursive Merge: Apply the same merging step recursively on the two smaller halves until the partition size is 1, resulting in a fully sorted sequence.

Complexity

Interactive visualization

Pseudocode

procedure bitonicSort(A, low, cnt, dir):
  if cnt > 1:
    k ← cnt / 2
    bitonicSort(A, low, k, true)       # Sort ascending
    bitonicSort(A, low + k, k, false)  # Sort descending
    bitonicMerge(A, low, cnt, dir)

procedure bitonicMerge(A, low, cnt, dir):
  if cnt > 1:
    k ← cnt / 2
    for i from low to low + k - 1:
      if dir == (A[i] > A[i + k]):
        swap A[i], A[i + k]
    bitonicMerge(A, low, k, dir)
    bitonicMerge(A, low + k, k, dir)

JavaScript implementation

function bitonicSort(arr) {
  const n = arr.length;
  
  function bitonicMerge(low, cnt, dir) {
    if (cnt > 1) {
      const k = cnt / 2;
      for (let i = low; i < low + k; i++) {
        if (dir === (arr[i] > arr[i + k])) {
          [arr[i], arr[i + k]] = [arr[i + k], arr[i]];
        }
      }
      bitonicMerge(low, k, dir);
      bitonicMerge(low + k, k, dir);
    }
  }
  
  function bitonicSortUtil(low, cnt, dir) {
    if (cnt > 1) {
      const k = cnt / 2;
      bitonicSortUtil(low, k, true);
      bitonicSortUtil(low + k, k, false);
      bitonicMerge(low, cnt, dir);
    }
  }
  
  bitonicSortUtil(0, n, true);
  return arr;
}

Pros and cons

When (not) to use it

• Graphics card & FPGA hardware: Ideal for hardware pipelines, vertex shaders, and parallel processing clusters where sorting networks can run concurrently.
• Standard CPU sorting: Avoid on general-purpose computers; Quicksort or Mergesort are significantly faster because they have higher cache locality and fewer comparison stages.