Bitonic Sort — VisualAlgorithms Docs

How it works

Builds and merges bitonic sequences through a fixed compare-exchange network. This arbitrary-length formulation splits on the greatest power of two below the range, so every comparator acts on real positions and the array is sorted in place. Highly parallelizable — the model behind GPU and hardware sorters.
Implementation

      
 function bitonicSort(arr, stats) {
  const n = arr.length;
  if (n < 2) {
    if (n === 1) markSorted(0);
    return;
  }
  const metrics = stats.educational.metrics;
  const recordMetric = (name, delta = 1) => {
    metrics[name] = (metrics[name] || 0) + delta;
  };
  function greatestPowerOfTwoBelow(value) {
    let power = 1;
    while (power < value) power <<= 1;
    return power >> 1;
  }
  function compareExchange(i, j, ascending) {
    compare(i, j);
    recordMetric('compareExchanges');
    if (ascending === arr[i] > arr[j]) {
      swap(i, j);
      const t = arr[i];
      arr[i] = arr[j];
      arr[j] = t;
      recordMetric('exchangeSwaps');
    }
  }
  function bitonicMerge(lo, count, ascending) {
    if (count <= 1) return;
    recordMetric('mergePasses');
    const m = greatestPowerOfTwoBelow(count);
    for (let i = lo; i < lo + count - m; i++) compareExchange(i, i + m, ascending);
    bitonicMerge(lo, m, ascending);
    bitonicMerge(lo + m, count - m, ascending);
  }
  function bitonicSort(lo, count, ascending) {
    if (count <= 1) return;
    recordMetric('sequenceBuilds');
    const m = count >> 1;
    bitonicSort(lo, m, !ascending);
    bitonicSort(lo + m, count - m, ascending);
    bitonicMerge(lo, count, ascending);
    checkpoint(Math.min(lo + count, n), n);
  }
  bitonicSort(0, n, true);
  for (let i = 0; i < n; i++) markSorted(i);
}
 def bitonicSort(arr, stats):
    def recordMetric(name, ):
        metrics[name] = ((metrics[name] or 0) + delta)

    def greatestPowerOfTwoBelow(value):
        power = 1
        while (power < value):
            power <<= 1
        return (power >> 1)

    def compareExchange(i, j, ascending):
        compare(i, j)
        recordMetric("compareExchanges")
        if (ascending == (arr[i] > arr[j])):
            swap(i, j)
            t = arr[i]
            arr[i] = arr[j]
            arr[j] = t
            recordMetric("exchangeSwaps")

    def bitonicMerge(lo, count, ascending):
        if (count <= 1):
            return
        recordMetric("mergePasses")
        m = greatestPowerOfTwoBelow(count)
        for i in range(lo, ((lo + count) - m)):
            compareExchange(i, (i + m), ascending)
        bitonicMerge(lo, m, ascending)
        bitonicMerge((lo + m), (count - m), ascending)

    def bitonicSort(lo, count, ascending):
        if (count <= 1):
            return
        recordMetric("sequenceBuilds")
        m = (count >> 1)
        bitonicSort(lo, m, not ascending)
        bitonicSort((lo + m), (count - m), ascending)
        bitonicMerge(lo, count, ascending)
        checkpoint(((lo + count) if (lo + count) <= n else n), n)

    if (n < 2):
        if (n == 1):
            markSorted(0)
        return
    bitonicSort(0, n, True)
    for i in range(n):
        markSorted(i)
 #include <vector>
#include <algorithm>
void recordMetric(int name, int );
int greatestPowerOfTwoBelow(int value);
void compareExchange(int i, int j, int ascending);
void bitonicMerge(int lo, int count, int ascending);
void bitonicSort(int lo, int count, int ascending);

void recordMetric(int name, int ) {
    metrics[name] = (((metrics[name]) != 0 ? (metrics[name]) : (0)) + delta);
}

int greatestPowerOfTwoBelow(int value) {
    int power = 1;
    while((power < value)) {
        power <<= 1;
    }
    return (power >> 1);
}

void compareExchange(int i, int j, int ascending) {
    compare(i, j);
    recordMetric("compareExchanges");
    if((ascending == (arr[i] > arr[j]))) {
        swap(i, j);
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
        recordMetric("exchangeSwaps");
    }
}

void bitonicMerge(int lo, int count, int ascending) {
    if((count <= 1)) {
        return;
    }
    recordMetric("mergePasses");
    int m = greatestPowerOfTwoBelow(count);
    for(int i=lo; i<((lo + count) - m); i++) {
        compareExchange(i, (i + m), ascending);
    }
    bitonicMerge(lo, m, ascending);
    bitonicMerge((lo + m), (count - m), ascending);
}

void bitonicSort(int lo, int count, int ascending) {
    if((count <= 1)) {
        return;
    }
    recordMetric("sequenceBuilds");
    int m = (count >> 1);
    bitonicSort(lo, m, !ascending);
    bitonicSort((lo + m), (count - m), ascending);
    bitonicMerge(lo, count, ascending);
    checkpoint((((lo + count)) < (n) ? ((lo + count)) : (n)), n);
}

void sort(std::vector<int>& arr, int n, int& comparisons, int& swaps) {
    if((n < 2)) {
        if((n == 1)) {
            markSorted(0);
        }
        return;
    }
    int metrics = educational.metrics;
    bitonicSort(0, n, 1);
    for(int i=0; i<n; i++) {
        markSorted(i);
    }
} void recordMetric(int name, int ) {
    metrics[name] = (((metrics[name]) != 0 ? (metrics[name]) : (0)) + delta);
}

int greatestPowerOfTwoBelow(int value) {
    int power = 1;
    while((power < value)) {
        power <<= 1;
    }
    return (power >> 1);
}

void compareExchange(int i, int j, int ascending) {
    compare(i, j);
    recordMetric("compareExchanges");
    if((ascending == (arr[i] > arr[j]))) {
        swap(i, j);
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
        recordMetric("exchangeSwaps");
    }
}

void bitonicMerge(int lo, int count, int ascending) {
    if((count <= 1)) {
        return;
    }
    recordMetric("mergePasses");
    int m = greatestPowerOfTwoBelow(count);
    for(int i=lo; i<((lo + count) - m); i++) {
        compareExchange(i, (i + m), ascending);
    }
    bitonicMerge(lo, m, ascending);
    bitonicMerge((lo + m), (count - m), ascending);
}

void bitonicSort(int lo, int count, int ascending) {
    if((count <= 1)) {
        return;
    }
    recordMetric("sequenceBuilds");
    int m = (count >> 1);
    bitonicSort(lo, m, !ascending);
    bitonicSort((lo + m), (count - m), ascending);
    bitonicMerge(lo, count, ascending);
    checkpoint(Math.Min((lo + count), n), n);
}

public void Sort(int[] arr, int n, dynamic stats) {
    if((n < 2)) {
        if((n == 1)) {
            markSorted(0);
        }
        return;
    }
    int metrics = stats.educational.metrics;
    bitonicSort(0, n, true);
    for(int i=0; i<n; i++) {
        markSorted(i);
    }
} #include <stdio.h>
void recordMetric(int name, int );
int greatestPowerOfTwoBelow(int value);
void compareExchange(int i, int j, int ascending);
void bitonicMerge(int lo, int count, int ascending);
void bitonicSort(int lo, int count, int ascending);

void recordMetric(int name, int ) {
    metrics[name] = (((metrics[name]) != 0 ? (metrics[name]) : (0)) + delta);
}

int greatestPowerOfTwoBelow(int value) {
    int power = 1;
    while((power < value)) {
        power <<= 1;
    }
    return (power >> 1);
}

void compareExchange(int i, int j, int ascending) {
    compare(i, j);
    recordMetric("compareExchanges");
    if((ascending == (arr[i] > arr[j]))) {
        swap(i, j);
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
        recordMetric("exchangeSwaps");
    }
}

void bitonicMerge(int lo, int count, int ascending) {
    if((count <= 1)) {
        return;
    }
    recordMetric("mergePasses");
    int m = greatestPowerOfTwoBelow(count);
    for(int i=lo; i<((lo + count) - m); i++) {
        compareExchange(i, (i + m), ascending);
    }
    bitonicMerge(lo, m, ascending);
    bitonicMerge((lo + m), (count - m), ascending);
}

void bitonicSort(int lo, int count, int ascending) {
    if((count <= 1)) {
        return;
    }
    recordMetric("sequenceBuilds");
    int m = (count >> 1);
    bitonicSort(lo, m, !ascending);
    bitonicSort((lo + m), (count - m), ascending);
    bitonicMerge(lo, count, ascending);
    checkpoint((((lo + count)) < (n) ? ((lo + count)) : (n)), n);
}

void sort(int arr[], int n, int* comparisons, int* swaps) {
    if((n < 2)) {
        if((n == 1)) {
            markSorted(0);
        }
        return;
    }
    int metrics = (*educational).metrics;
    bitonicSort(0, n, 1);
    for(int i=0; i<n; i++) {
        markSorted(i);
    }
} 