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) {
  const n = arr.length;
  const ce = (i, j, asc) => {            // compare-exchange in a direction
    if (asc === arr[i] > arr[j]) [arr[i], arr[j]] = [arr[j], arr[i]];
  };
  const pow2Below = (v) => { let p = 1; while (p < v) p <<= 1; return p >> 1; };
  function merge(lo, cnt, asc) {
    if (cnt <= 1) return;
    const m = pow2Below(cnt);            // works for any length, not just 2^k
    for (let i = lo; i < lo + cnt - m; i++) ce(i, i + m, asc);
    merge(lo, m, asc);
    merge(lo + m, cnt - m, asc);
  }
  function sort(lo, cnt, asc) {
    if (cnt <= 1) return;
    const m = cnt >> 1;
    sort(lo, m, !asc);                    // build a descending then ascending run
    sort(lo + m, cnt - m, asc);
    merge(lo, cnt, asc);                  // ...then merge the bitonic sequence
  }
  sort(0, n, true);
} function bitonicSort(arr) {
  const n = arr.length;
  const ce = (i, j, asc) => {            // compare-exchange in a direction
    if (asc === arr[i] > arr[j]) [arr[i], arr[j]] = [arr[j], arr[i]];
  };
  const pow2Below = (v) => { let p = 1; while (p < v) p <<= 1; return p >> 1; };
  function merge(lo, cnt, asc) {
    if (cnt <= 1) return;
    const m = pow2Below(cnt);            // works for any length, not just 2^k
    for (let i = lo; i < lo + cnt - m; i++) ce(i, i + m, asc);
    merge(lo, m, asc);
    merge(lo + m, cnt - m, asc);
  }
  function sort(lo, cnt, asc) {
    if (cnt <= 1) return;
    const m = cnt >> 1;
    sort(lo, m, !asc);                    // build a descending then ascending run
    sort(lo + m, cnt - m, asc);
    merge(lo, cnt, asc);                  // ...then merge the bitonic sequence
  }
  sort(0, n, true);
} function bitonicSort(arr) {
  const n = arr.length;
  const ce = (i, j, asc) => {            // compare-exchange in a direction
    if (asc === arr[i] > arr[j]) [arr[i], arr[j]] = [arr[j], arr[i]];
  };
  const pow2Below = (v) => { let p = 1; while (p < v) p <<= 1; return p >> 1; };
  function merge(lo, cnt, asc) {
    if (cnt <= 1) return;
    const m = pow2Below(cnt);            // works for any length, not just 2^k
    for (let i = lo; i < lo + cnt - m; i++) ce(i, i + m, asc);
    merge(lo, m, asc);
    merge(lo + m, cnt - m, asc);
  }
  function sort(lo, cnt, asc) {
    if (cnt <= 1) return;
    const m = cnt >> 1;
    sort(lo, m, !asc);                    // build a descending then ascending run
    sort(lo + m, cnt - m, asc);
    merge(lo, cnt, asc);                  // ...then merge the bitonic sequence
  }
  sort(0, n, true);
} function bitonicSort(arr) {
  const n = arr.length;
  const ce = (i, j, asc) => {            // compare-exchange in a direction
    if (asc === arr[i] > arr[j]) [arr[i], arr[j]] = [arr[j], arr[i]];
  };
  const pow2Below = (v) => { let p = 1; while (p < v) p <<= 1; return p >> 1; };
  function merge(lo, cnt, asc) {
    if (cnt <= 1) return;
    const m = pow2Below(cnt);            // works for any length, not just 2^k
    for (let i = lo; i < lo + cnt - m; i++) ce(i, i + m, asc);
    merge(lo, m, asc);
    merge(lo + m, cnt - m, asc);
  }
  function sort(lo, cnt, asc) {
    if (cnt <= 1) return;
    const m = cnt >> 1;
    sort(lo, m, !asc);                    // build a descending then ascending run
    sort(lo + m, cnt - m, asc);
    merge(lo, cnt, asc);                  // ...then merge the bitonic sequence
  }
  sort(0, n, true);
} function bitonicSort(arr) {
  const n = arr.length;
  const ce = (i, j, asc) => {            // compare-exchange in a direction
    if (asc === arr[i] > arr[j]) [arr[i], arr[j]] = [arr[j], arr[i]];
  };
  const pow2Below = (v) => { let p = 1; while (p < v) p <<= 1; return p >> 1; };
  function merge(lo, cnt, asc) {
    if (cnt <= 1) return;
    const m = pow2Below(cnt);            // works for any length, not just 2^k
    for (let i = lo; i < lo + cnt - m; i++) ce(i, i + m, asc);
    merge(lo, m, asc);
    merge(lo + m, cnt - m, asc);
  }
  function sort(lo, cnt, asc) {
    if (cnt <= 1) return;
    const m = cnt >> 1;
    sort(lo, m, !asc);                    // build a descending then ascending run
    sort(lo + m, cnt - m, asc);
    merge(lo, cnt, asc);                  // ...then merge the bitonic sequence
  }
  sort(0, n, true);
} 