Bitonic Sort

Builds bitonic sequences and merges them recursively. Parallelizable, requires power-of-2 length (auto-padded here).

Best: O(log² n) · Avg: O(log² n) · Worst: O(log² n) · Space: O(n log n)

75
27
58
37
14
19
13
68
97
55
89
61
47
55
65
0
Speed5
Size15
TypeScript
function bitonicSort(arr: number[], lo = 0, cnt = arr.length, dir = true) {
  if (cnt > 1) {
    const k = Math.floor(cnt / 2);
    bitonicSort(arr, lo, k, true);
    bitonicSort(arr, lo + k, k, false);
    bitonicMerge(arr, lo, cnt, dir);
  }
  return arr;
}
function bitonicMerge(arr: number[], lo: number, cnt: number, dir: boolean) {
  if (cnt > 1) {
    const k = Math.floor(cnt / 2);
    for (let i = lo; i < lo + k; i++)
      compareSwap(arr, i, i + k, dir);
    bitonicMerge(arr, lo, k, dir);
    bitonicMerge(arr, lo + k, k, dir);
  }
}
function compareSwap(a: number[], i: number, j: number, dir: boolean) {
  if ((a[i] > a[j]) === dir) [a[i], a[j]] = [a[j], a[i]];
}