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, stats) { const n = arr.length; if (n < 2) { if (n === 1) markSorted(0); return; } 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; } } function merge(i, li, j, lj) { if (li < 1 || lj < 1) return; if (li === 1 && lj === 1) { compareExchange(i, j); } else if (li === 1 && lj === 2) { compareExchange(i, j + 1); compareExchange(i, j); } else if (li === 2 && lj === 1) { compareExchange(i, j); compareExchange(i + 1, j); } else { const imid = li >> 1; const jmid = (li & 1) === 1 ? lj >> 1 : lj + 1 >> 1; merge(i, imid, j, jmid); merge(i + imid, li - imid, j + jmid, lj - jmid); merge(i + imid, li - imid, j, jmid); } } function sort(i, length) { if (length < 2) return; const m = length >> 1; sort(i, m); sort(i + m, length - m); merge(i, m, i + m, length - m); checkpoint(i + length, n); } sort(0, n); for (let i = 0; i < n; i++) markSorted(i); }
def boseNelsonSort(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 def merge(i, li, j, lj): if ((li < 1) or (lj < 1)): return if ((li == 1) and (lj == 1)): compareExchange(i, j) elif ((li == 1) and (lj == 2)): compareExchange(i, (j + 1)) compareExchange(i, j) else: if ((li == 2) and (lj == 1)): compareExchange(i, j) compareExchange((i + 1), j) else: imid = (li >> 1) jmid = ((lj >> 1) if ((li & 1) == 1) else ((lj + 1) >> 1)) merge(i, imid, j, jmid) merge((i + imid), (li - imid), (j + jmid), (lj - jmid)) merge((i + imid), (li - imid), j, jmid) def sort(i, length): if (length < 2): return m = (length >> 1) sort(i, m) sort((i + m), (length - m)) merge(i, m, (i + m), (length - m)) checkpoint((i + length), n) if (n < 2): if (n == 1): markSorted(0) return sort(0, n) for i in range(n): markSorted(i)
#include <vector> #include <algorithm> void compareExchange(int i, int j); void merge(int i, int li, int j, int lj); void sort(int i, int length); 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 merge(int i, int li, int j, int lj) { if(((li < 1) || (lj < 1))) { return; } if(((li == 1) && (lj == 1))) { compareExchange(i, j); } else if(((li == 1) && (lj == 2))) { compareExchange(i, (j + 1)); compareExchange(i, j); } else { if(((li == 2) && (lj == 1))) { compareExchange(i, j); compareExchange((i + 1), j); } else { int imid = (li >> 1); int jmid = ((((li & 1) == 1)) ? ((lj >> 1)) : (((lj + 1) >> 1))); merge(i, imid, j, jmid); merge((i + imid), (li - imid), (j + jmid), (lj - jmid)); merge((i + imid), (li - imid), j, jmid); } } } void sort(int i, int length) { if((length < 2)) { return; } int m = (length >> 1); sort(i, m); sort((i + m), (length - m)); merge(i, m, (i + m), (length - m)); checkpoint((i + length), n); } void sort(std::vector<int>& arr, int n, int& comparisons, int& swaps) { if((n < 2)) { if((n == 1)) { markSorted(0); } return; } sort(0, n); 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; } } void merge(int i, int li, int j, int lj) { if(((li < 1) || (lj < 1))) { return; } if(((li == 1) && (lj == 1))) { compareExchange(i, j); } else if(((li == 1) && (lj == 2))) { compareExchange(i, (j + 1)); compareExchange(i, j); } else { if(((li == 2) && (lj == 1))) { compareExchange(i, j); compareExchange((i + 1), j); } else { int imid = (li >> 1); int jmid = ((((li & 1) == 1)) ? ((lj >> 1)) : (((lj + 1) >> 1))); merge(i, imid, j, jmid); merge((i + imid), (li - imid), (j + jmid), (lj - jmid)); merge((i + imid), (li - imid), j, jmid); } } } void sort(int i, int length) { if((length < 2)) { return; } int m = (length >> 1); sort(i, m); sort((i + m), (length - m)); merge(i, m, (i + m), (length - m)); checkpoint((i + length), n); } public void Sort(int[] arr, int n, dynamic stats) { if((n < 2)) { if((n == 1)) { markSorted(0); } return; } sort(0, n); for(int i=0; i<n; i++) { markSorted(i); } }
#include <stdio.h> void compareExchange(int i, int j); void merge(int i, int li, int j, int lj); void sort(int i, int length); 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 merge(int i, int li, int j, int lj) { if(((li < 1) || (lj < 1))) { return; } if(((li == 1) && (lj == 1))) { compareExchange(i, j); } else if(((li == 1) && (lj == 2))) { compareExchange(i, (j + 1)); compareExchange(i, j); } else { if(((li == 2) && (lj == 1))) { compareExchange(i, j); compareExchange((i + 1), j); } else { int imid = (li >> 1); int jmid = ((((li & 1) == 1)) ? ((lj >> 1)) : (((lj + 1) >> 1))); merge(i, imid, j, jmid); merge((i + imid), (li - imid), (j + jmid), (lj - jmid)); merge((i + imid), (li - imid), j, jmid); } } } void sort(int i, int length) { if((length < 2)) { return; } int m = (length >> 1); sort(i, m); sort((i + m), (length - m)); merge(i, m, (i + m), (length - m)); checkpoint((i + length), n); } void sort(int arr[], int n, int* comparisons, int* swaps) { if((n < 2)) { if((n == 1)) { markSorted(0); } return; } sort(0, n); for(int i=0; i<n; i++) { markSorted(i); } }