Bose-Nelson Sort — VisualAlgorithms Docs

How it works

A data-oblivious sorting network from Bose and Nelson (1962). A recursive merge schedule emits a fixed list of compare-exchanges that is correct for any array length, so it sorts in place with no extra buffers and a comparison pattern independent of the data.
Implementation

      
 function boseNelsonSort(arr) {
  const n = arr.length;
  // Compare-exchange: route the smaller value to the lower index.
  function ce(i, j) {
    if (arr[i] > arr[j]) [arr[i], arr[j]] = [arr[j], arr[i]];
  }
  // Merge a sorted run of length li at i with a sorted run of length lj at j.
  function merge(i, li, j, lj) {
    if (li < 1 || lj < 1) return;
    if (li === 1 && lj === 1) ce(i, j);
    else if (li === 1 && lj === 2) { ce(i, j + 1); ce(i, j); }
    else if (li === 2 && lj === 1) { ce(i, j); ce(i + 1, j); }
    else {
      const a = li >> 1;
      const b = (li & 1) ? (lj >> 1) : ((lj + 1) >> 1);
      merge(i, a, j, b);
      merge(i + a, li - a, j + b, lj - b);
      merge(i + a, li - a, j, b);
    }
  }
  function sort(i, len) {
    if (len < 2) return;
    const m = len >> 1;
    sort(i, m);
    sort(i + m, len - m);
    merge(i, m, i + m, len - m);
  }
  sort(0, n); // data-oblivious: the comparator schedule never depends on values
} function boseNelsonSort(arr) {
  const n = arr.length;
  // Compare-exchange: route the smaller value to the lower index.
  function ce(i, j) {
    if (arr[i] > arr[j]) [arr[i], arr[j]] = [arr[j], arr[i]];
  }
  // Merge a sorted run of length li at i with a sorted run of length lj at j.
  function merge(i, li, j, lj) {
    if (li < 1 || lj < 1) return;
    if (li === 1 && lj === 1) ce(i, j);
    else if (li === 1 && lj === 2) { ce(i, j + 1); ce(i, j); }
    else if (li === 2 && lj === 1) { ce(i, j); ce(i + 1, j); }
    else {
      const a = li >> 1;
      const b = (li & 1) ? (lj >> 1) : ((lj + 1) >> 1);
      merge(i, a, j, b);
      merge(i + a, li - a, j + b, lj - b);
      merge(i + a, li - a, j, b);
    }
  }
  function sort(i, len) {
    if (len < 2) return;
    const m = len >> 1;
    sort(i, m);
    sort(i + m, len - m);
    merge(i, m, i + m, len - m);
  }
  sort(0, n); // data-oblivious: the comparator schedule never depends on values
} function boseNelsonSort(arr) {
  const n = arr.length;
  // Compare-exchange: route the smaller value to the lower index.
  function ce(i, j) {
    if (arr[i] > arr[j]) [arr[i], arr[j]] = [arr[j], arr[i]];
  }
  // Merge a sorted run of length li at i with a sorted run of length lj at j.
  function merge(i, li, j, lj) {
    if (li < 1 || lj < 1) return;
    if (li === 1 && lj === 1) ce(i, j);
    else if (li === 1 && lj === 2) { ce(i, j + 1); ce(i, j); }
    else if (li === 2 && lj === 1) { ce(i, j); ce(i + 1, j); }
    else {
      const a = li >> 1;
      const b = (li & 1) ? (lj >> 1) : ((lj + 1) >> 1);
      merge(i, a, j, b);
      merge(i + a, li - a, j + b, lj - b);
      merge(i + a, li - a, j, b);
    }
  }
  function sort(i, len) {
    if (len < 2) return;
    const m = len >> 1;
    sort(i, m);
    sort(i + m, len - m);
    merge(i, m, i + m, len - m);
  }
  sort(0, n); // data-oblivious: the comparator schedule never depends on values
} function boseNelsonSort(arr) {
  const n = arr.length;
  // Compare-exchange: route the smaller value to the lower index.
  function ce(i, j) {
    if (arr[i] > arr[j]) [arr[i], arr[j]] = [arr[j], arr[i]];
  }
  // Merge a sorted run of length li at i with a sorted run of length lj at j.
  function merge(i, li, j, lj) {
    if (li < 1 || lj < 1) return;
    if (li === 1 && lj === 1) ce(i, j);
    else if (li === 1 && lj === 2) { ce(i, j + 1); ce(i, j); }
    else if (li === 2 && lj === 1) { ce(i, j); ce(i + 1, j); }
    else {
      const a = li >> 1;
      const b = (li & 1) ? (lj >> 1) : ((lj + 1) >> 1);
      merge(i, a, j, b);
      merge(i + a, li - a, j + b, lj - b);
      merge(i + a, li - a, j, b);
    }
  }
  function sort(i, len) {
    if (len < 2) return;
    const m = len >> 1;
    sort(i, m);
    sort(i + m, len - m);
    merge(i, m, i + m, len - m);
  }
  sort(0, n); // data-oblivious: the comparator schedule never depends on values
} function boseNelsonSort(arr) {
  const n = arr.length;
  // Compare-exchange: route the smaller value to the lower index.
  function ce(i, j) {
    if (arr[i] > arr[j]) [arr[i], arr[j]] = [arr[j], arr[i]];
  }
  // Merge a sorted run of length li at i with a sorted run of length lj at j.
  function merge(i, li, j, lj) {
    if (li < 1 || lj < 1) return;
    if (li === 1 && lj === 1) ce(i, j);
    else if (li === 1 && lj === 2) { ce(i, j + 1); ce(i, j); }
    else if (li === 2 && lj === 1) { ce(i, j); ce(i + 1, j); }
    else {
      const a = li >> 1;
      const b = (li & 1) ? (lj >> 1) : ((lj + 1) >> 1);
      merge(i, a, j, b);
      merge(i + a, li - a, j + b, lj - b);
      merge(i + a, li - a, j, b);
    }
  }
  function sort(i, len) {
    if (len < 2) return;
    const m = len >> 1;
    sort(i, m);
    sort(i + m, len - m);
    merge(i, m, i + m, len - m);
  }
  sort(0, n); // data-oblivious: the comparator schedule never depends on values
} 