Pairwise Sorting Network — VisualAlgorithms Docs

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 pairwiseNetworkSort(arr, stats) {
  const n = arr.length;
  if (n < 2) {
    if (n === 1) markSorted(0);
    return;
  }
  let k = 1;
  while (k < n) k <<= 1;
  function compareExchange(i, j) {
    compare(i, j);
    if (arr[i] > arr[j]) {
      swap(i, j);
      const t = arr[i];
      arr[i] = arr[j];
      arr[j] = t;
    }
  }
  for (let p = k >> 1; p >= 1; p >>= 1) {
    for (let a = 0; a < n; a += p * 2) {
      for (let b = 0; b < p; b++) {
        const j = a + b + p;
        if (j < n) compareExchange(a + b, j);
      }
    }
    for (let q = k >> 1; q >= p * 2; q >>= 1) {
      for (let c = 0; c < n; c += p * 2) {
        for (let d = 0; d < p; d++) {
          const j = c + d + q;
          if (j < n) compareExchange(c + d + p, j);
        }
      }
    }
    checkpoint(k - p, k);
  }
  for (let i = 0; i < n; i++) markSorted(i);
}
 def pairwiseNetworkSort(arr, stats):
    def compareExchange(i, j):
        compare(i, j)
        if (arr[i] > arr[j]):
            swap(i, j)
            t = arr[i]
            arr[i] = arr[j]
            arr[j] = t

    if (n < 2):
        if (n == 1):
            markSorted(0)
        return
    k = 1
    while (k < n):
        k <<= 1
    p = (k >> 1)
    while (p >= 1):
        for a in range(0, n, (p * 2)):
            for b in range(p):
                j = ((a + b) + p)
                if (j < n):
                    compareExchange((a + b), j)
        q = (k >> 1)
        while (q >= (p * 2)):
            for c in range(0, n, (p * 2)):
                for d in range(p):
                    j = ((c + d) + q)
                    if (j < n):
                        compareExchange(((c + d) + p), j)
            q >>= 1
        checkpoint((k - p), k)
        p >>= 1
    for i in range(n):
        markSorted(i)
 #include <vector>
#include <algorithm>
void compareExchange(int i, int j);

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

void sort(std::vector<int>& arr, int n, int& comparisons, int& swaps) {
    if((n < 2)) {
        if((n == 1)) {
            markSorted(0);
        }
        return;
    }
    int k = 1;
    while((k < n)) {
        k <<= 1;
    }
    for(int p=(k >> 1); (p >= 1); p >>= 1) {
        for(int a=0; a<n; a+=(p * 2)) {
            for(int b=0; b<p; b++) {
                int j = ((a + b) + p);
                if((j < n)) {
                    compareExchange((a + b), j);
                }
            }
        }
        for(int q=(k >> 1); (q >= (p * 2)); q >>= 1) {
            for(int c=0; c<n; c+=(p * 2)) {
                for(int d=0; d<p; d++) {
                    int j = ((c + d) + q);
                    if((j < n)) {
                        compareExchange(((c + d) + p), j);
                    }
                }
            }
        }
        checkpoint((k - p), k);
    }
    for(int i=0; i<n; i++) {
        markSorted(i);
    }
} void compareExchange(int i, int j) {
    compare(i, j);
    if((arr[i] > arr[j])) {
        swap(i, j);
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
}

public void Sort(int[] arr, int n, dynamic stats) {
    if((n < 2)) {
        if((n == 1)) {
            markSorted(0);
        }
        return;
    }
    int k = 1;
    while((k < n)) {
        k <<= 1;
    }
    for(int p=(k >> 1); (p >= 1); p >>= 1) {
        for(int a=0; a<n; a+=(p * 2)) {
            for(int b=0; b<p; b++) {
                int j = ((a + b) + p);
                if((j < n)) {
                    compareExchange((a + b), j);
                }
            }
        }
        for(int q=(k >> 1); (q >= (p * 2)); q >>= 1) {
            for(int c=0; c<n; c+=(p * 2)) {
                for(int d=0; d<p; d++) {
                    int j = ((c + d) + q);
                    if((j < n)) {
                        compareExchange(((c + d) + p), j);
                    }
                }
            }
        }
        checkpoint((k - p), k);
    }
    for(int i=0; i<n; i++) {
        markSorted(i);
    }
} #include <stdio.h>
void compareExchange(int i, int j);

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

void sort(int arr[], int n, int* comparisons, int* swaps) {
    if((n < 2)) {
        if((n == 1)) {
            markSorted(0);
        }
        return;
    }
    int k = 1;
    while((k < n)) {
        k <<= 1;
    }
    for(int p=(k >> 1); (p >= 1); p >>= 1) {
        for(int a=0; a<n; a+=(p * 2)) {
            for(int b=0; b<p; b++) {
                int j = ((a + b) + p);
                if((j < n)) {
                    compareExchange((a + b), j);
                }
            }
        }
        for(int q=(k >> 1); (q >= (p * 2)); q >>= 1) {
            for(int c=0; c<n; c+=(p * 2)) {
                for(int d=0; d<p; d++) {
                    int j = ((c + d) + q);
                    if((j < n)) {
                        compareExchange(((c + d) + p), j);
                    }
                }
            }
        }
        checkpoint((k - p), k);
    }
    for(int i=0; i<n; i++) {
        markSorted(i);
    }
} 