Skip to content

Instantly share code, notes, and snippets.

@mourner
Last active April 1, 2020 14:16
Show Gist options
  • Save mourner/a1e0e8f48e0125c541d88199ce0b6479 to your computer and use it in GitHub Desktop.
Save mourner/a1e0e8f48e0125c541d88199ce0b6479 to your computer and use it in GitHub Desktop.
Fast MSD in-place radix sort for Uint32 numbers in JavaScript
const radixSort = require('./index.js');
const N = 10000000;
const arr = new Uint32Array(N);
for (let i = 0; i < N; i++) arr[i] = Math.floor(Math.random() * 4294967295);
console.log(`sorting ${N.toLocaleString()} uint32 numbers`);
// warmup
radixSort(arr.slice());
const arr2 = arr.slice();
const sorted = arr.slice().sort();
console.time('radix sort');
radixSort(arr);
console.timeEnd('radix sort');
for (let i = 0; i < N; i++) if (arr[i] !== sorted[i]) throw new Error('Not sorted.');
console.time('native sort');
arr2.sort();
console.timeEnd('native sort');
module.exports = radixSort;
const last = new Uint32Array(256);
const pointer0 = new Uint32Array(256);
const pointer8 = new Uint32Array(256);
const pointer16 = new Uint32Array(256);
const pointer24 = new Uint32Array(256);
function radixSort(arr, start = 0, end = arr.length, shift = 24) {
const ptr =
shift === 0 ? pointer0 :
shift === 8 ? pointer8 :
shift === 16 ? pointer16 : pointer24;
for (let x = start; x < end; ++x) last[(arr[x] >> shift) & 0xFF]++;
last[0] += start;
ptr[0] = start;
for (let x = 1; x < 256; ++x) {
ptr[x] = last[x - 1];
last[x] += last[x - 1];
}
for (let x = 0; x < 256; ++x) {
let i = ptr[x];
while (i !== last[x]) {
let value = arr[i], y;
while ((y = (value >> shift) & 0xFF) !== x) {
value = arr[ptr[y]];
swap(arr, i, ptr[y]++);
}
i++;
}
ptr[x] = i;
last[x] = 0;
}
if (shift === 0) return;
for (let x = 0; x < 256; ++x) {
const i = x > 0 ? ptr[x - 1] : start;
const j = ptr[x];
if (j - i > 64) {
radixSort(arr, i, j, shift - 8);
} else {
insertionSort(arr, i, j);
}
}
}
function insertionSort(arr, start, end) {
for (let x = start + 1; x < end; ++x) {
for (let y = x; y > start && arr[y - 1] > arr[y]; y--) swap(arr, y, y - 1);
}
}
function swap(arr, i, j) {
const temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment