Last active
April 1, 2020 14:16
-
-
Save mourner/a1e0e8f48e0125c541d88199ce0b6479 to your computer and use it in GitHub Desktop.
Fast MSD in-place radix sort for Uint32 numbers in JavaScript
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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'); |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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