How it works
Ian Parberry's pairwise sorting network (1992): a data-oblivious network with the same number of comparators and depth as Batcher's odd-even mergesort, but a distinct structure. Compare-exchanges that fall outside the array are pruned, so the fixed schedule sorts any length in place with no extra memory.
Implementation
function pairwiseSort(arr) { const n = arr.length; let k = 1; while (k < n) k <<= 1; // round the length up to a power of two const ce = (i, j) => { // compare-exchange (smaller stays low) if (arr[i] > arr[j]) [arr[i], arr[j]] = [arr[j], arr[i]]; }; for (let p = k >> 1; p >= 1; p >>= 1) { // Stage 1: compare every channel with its partner p positions away. for (let a = 0; a < n; a += 2 * p) for (let b = 0; b < p; b++) if (a + b + p < n) ce(a + b, a + b + p); // Stage 2: merge the sorted pairs into order. for (let q = k >> 1; q >= 2 * p; q >>= 1) for (let c = 0; c < n; c += 2 * p) for (let d = 0; d < p; d++) if (c + d + q < n) ce(c + d + p, c + d + q); } // Comparators landing outside [0, n) are skipped, so any length sorts in place. }
function pairwiseSort(arr) { const n = arr.length; let k = 1; while (k < n) k <<= 1; // round the length up to a power of two const ce = (i, j) => { // compare-exchange (smaller stays low) if (arr[i] > arr[j]) [arr[i], arr[j]] = [arr[j], arr[i]]; }; for (let p = k >> 1; p >= 1; p >>= 1) { // Stage 1: compare every channel with its partner p positions away. for (let a = 0; a < n; a += 2 * p) for (let b = 0; b < p; b++) if (a + b + p < n) ce(a + b, a + b + p); // Stage 2: merge the sorted pairs into order. for (let q = k >> 1; q >= 2 * p; q >>= 1) for (let c = 0; c < n; c += 2 * p) for (let d = 0; d < p; d++) if (c + d + q < n) ce(c + d + p, c + d + q); } // Comparators landing outside [0, n) are skipped, so any length sorts in place. }
function pairwiseSort(arr) { const n = arr.length; let k = 1; while (k < n) k <<= 1; // round the length up to a power of two const ce = (i, j) => { // compare-exchange (smaller stays low) if (arr[i] > arr[j]) [arr[i], arr[j]] = [arr[j], arr[i]]; }; for (let p = k >> 1; p >= 1; p >>= 1) { // Stage 1: compare every channel with its partner p positions away. for (let a = 0; a < n; a += 2 * p) for (let b = 0; b < p; b++) if (a + b + p < n) ce(a + b, a + b + p); // Stage 2: merge the sorted pairs into order. for (let q = k >> 1; q >= 2 * p; q >>= 1) for (let c = 0; c < n; c += 2 * p) for (let d = 0; d < p; d++) if (c + d + q < n) ce(c + d + p, c + d + q); } // Comparators landing outside [0, n) are skipped, so any length sorts in place. }
function pairwiseSort(arr) { const n = arr.length; let k = 1; while (k < n) k <<= 1; // round the length up to a power of two const ce = (i, j) => { // compare-exchange (smaller stays low) if (arr[i] > arr[j]) [arr[i], arr[j]] = [arr[j], arr[i]]; }; for (let p = k >> 1; p >= 1; p >>= 1) { // Stage 1: compare every channel with its partner p positions away. for (let a = 0; a < n; a += 2 * p) for (let b = 0; b < p; b++) if (a + b + p < n) ce(a + b, a + b + p); // Stage 2: merge the sorted pairs into order. for (let q = k >> 1; q >= 2 * p; q >>= 1) for (let c = 0; c < n; c += 2 * p) for (let d = 0; d < p; d++) if (c + d + q < n) ce(c + d + p, c + d + q); } // Comparators landing outside [0, n) are skipped, so any length sorts in place. }
function pairwiseSort(arr) { const n = arr.length; let k = 1; while (k < n) k <<= 1; // round the length up to a power of two const ce = (i, j) => { // compare-exchange (smaller stays low) if (arr[i] > arr[j]) [arr[i], arr[j]] = [arr[j], arr[i]]; }; for (let p = k >> 1; p >= 1; p >>= 1) { // Stage 1: compare every channel with its partner p positions away. for (let a = 0; a < n; a += 2 * p) for (let b = 0; b < p; b++) if (a + b + p < n) ce(a + b, a + b + p); // Stage 2: merge the sorted pairs into order. for (let q = k >> 1; q >= 2 * p; q >>= 1) for (let c = 0; c < n; c += 2 * p) for (let d = 0; d < p; d++) if (c + d + q < n) ce(c + d + p, c + d + q); } // Comparators landing outside [0, n) are skipped, so any length sorts in place. }