I have been looking around the web for a while and I am wondering if there is a 'stable' defacto implementation of Radix Sort that is generally used?
Two classifications of radix sorts are least significant digit (LSD) radix sorts and most significant digit (MSD) radix sorts.
Looking for an example of LSD or MSD.
My version is more verbose, but executes quickly even for large number of items:
var testArray = [ 331, 454, 230, 34, 343, 45, 59, 453, 345, 231, 9 ];
function radixBucketSort (arr) {
var idx1, idx2, idx3, len1, len2, radix, radixKey;
var radices = {}, buckets = {}, num, curr;
var currLen, radixStr, currBucket;
len1 = arr.length;
len2 = 10; // radix sort uses ten buckets
// find the relevant radices to process for efficiency
for (idx1 = 0;idx1 < len1;idx1++) {
radices[arr[idx1].toString().length] = 0;
}
// loop for each radix. For each radix we put all the items
// in buckets, and then pull them out of the buckets.
for (radix in radices) {
// put each array item in a bucket based on its radix value
len1 = arr.length;
for (idx1 = 0;idx1 < len1;idx1++) {
curr = arr[idx1];
// item length is used to find its current radix value
currLen = curr.toString().length;
// only put the item in a radix bucket if the item
// key is as long as the radix
if (currLen >= radix) {
// radix starts from beginning of key, so need to
// adjust to get redix values from start of stringified key
radixKey = curr.toString()[currLen - radix];
// create the bucket if it does not already exist
if (!buckets.hasOwnProperty(radixKey)) {
buckets[radixKey] = [];
}
// put the array value in the bucket
buckets[radixKey].push(curr);
} else {
if (!buckets.hasOwnProperty('0')) {
buckets['0'] = [];
}
buckets['0'].push(curr);
}
}
// for current radix, items are in buckets, now put them
// back in the array based on their buckets
// this index moves us through the array as we insert items
idx1 = 0;
// go through all the buckets
for (idx2 = 0;idx2 < len2;idx2++) {
// only process buckets with items
if (buckets[idx2] != null) {
currBucket = buckets[idx2];
// insert all bucket items into array
len1 = currBucket.length;
for (idx3 = 0;idx3 < len1;idx3++) {
arr[idx1++] = currBucket[idx3];
}
}
}
buckets = {};
}
}
radixBucketSort(testArray);
console.dir(testArray);
The following function does LSB radix sort on Uint32 values. It is faster than the built-in sort function, by the way.
It uses typed arrays to improve performance, but works just as fine if you pass plain arrays, as long as they contain only 32 bit values:
function radixSortUint32(input) {
const arrayConstr = input.length < (1 << 16) ?
Uint16Array :
Uint32Array;
const numberOfBins = 256 * 4;
let count = new arrayConstr(numberOfBins);
let output = new Uint32Array(input.length);
// count all bytes in one pass
for (let i = 0; i < input.length; i++) {
let val = input[i];
count[val & 0xFF]++;
count[((val >> 8) & 0xFF) + 256]++;
count[((val >> 16) & 0xFF) + 512]++;
count[((val >> 24) & 0xFF) + 768]++;
}
// create summed array
for (let j = 0; j < 4; j++) {
let t = 0,
sum = 0,
offset = j * 256;
for (let i = 0; i < 256; i++) {
t = count[i + offset];
count[i + offset] = sum;
sum += t;
}
}
for (let i = 0; i < input.length; i++) {
let val = input[i];
output[count[val & 0xFF]++] = val;
}
for (let i = 0; i < input.length; i++) {
let val = output[i];
input[count[((val >> 8) & 0xFF) + 256]++] = val;
}
for (let i = 0; i < input.length; i++) {
let val = input[i];
output[count[((val >> 16) & 0xFF) + 512]++] = val;
}
for (let i = 0; i < input.length; i++) {
let val = output[i];
input[count[((val >> 24) & 0xFF) + 768]++] = val;
}
return input;
}
Here's how you re-use the above for Int32 values:
function radixSortInt32(input) {
// make use of ArrayBuffer to "reinterpret cast"
// the Int32Array as a Uint32Array
let uinput = input.buffer ?
new Uint32Array(input.buffer):
Uint32Array.from(input);
// adjust to positive nrs
for (let i = 0; i < uinput.length; i++) {
uinput[i] += 0x80000000;
}
// re-use radixSortUint32
radixSortUint32(uinput);
// adjust back to signed nrs
for (let i = 0; i < uinput.length; i++) {
uinput[i] -= 0x80000000;
}
// for plain arrays, fake in-place behaviour
if (input.buffer === undefined){
for (let i = 0; i < input.length; i++){
input[i] = uinput[i];
}
}
return input;
}
And a similar trick for Float32 values:
function radixSortFloat32(input) {
// make use of ArrayBuffer to "reinterpret cast"
// the Float32Array as a Uint32Array
let uinput = input.buffer ?
new Uint32Array(input.buffer) :
new Uint32Array(Float32Array.from(input).buffer);
// Similar to radixSortInt32, but uses a more complicated trick
// See: http://stereopsis.com/radixSort.html
for (let i = 0; i < uinput.length; i++) {
if (uinput[i] & 0x80000000) {
uinput[i] ^= 0xFFFFFFFF;
} else {
uinput[i] ^= 0x80000000;
}
}
// re-use radixSortUint32
radixSortUint32(uinput);
// adjust back to original floating point nrs
for (let i = 0; i < uinput.length; i++) {
if (uinput[i] & 0x80000000) {
uinput[i] ^= 0x80000000;
} else {
uinput[i] ^= 0xFFFFFFFF;
}
}
if (input.buffer === undefined){
let floatTemp = new Float32Array(uinput.buffer);
for(let i = 0; i < input.length; i++){
input[i] = floatTemp[i];
}
}
return input;
}
I made a set of these functions that work with all TypedArrays that are 32 bits or less. That is:
Full gist here. I might have a go at Float64 later, then we would have support for all javascript numbers, basically.
TypedArray benchmarks shows radix beats the built-in sort function.
It's faster with plain arrays too, although not quite as much because of the added overhead
Javascript LSD sort:
var counter = [[]];
function sortLSD(array, maxDigitSymbols) {
var mod = 10;
var dev = 1;
for (var i = 0; i < maxDigitSymbols; i++, dev *= 10, mod *= 10) {
for (var j = 0; j < array.length; j++) {
var bucket = parseInt((array[j] % mod) / dev);
if (counter[bucket] == null ) {
counter[bucket] = [];
}
counter[bucket].push(array[j]);
}
var pos = 0;
for (var j = 0; j < counter.length; j++) {
var value = null ;
if (counter[j] != null ) {
while ((value = counter[j].shift()) != null ) {
array[pos++] = value;
}
}
}
}
return array;
}
var test = [22, 1,2,9,3,2,5,14,66];
console.log(sortLSD(test, 2));
With below code you can pass array with large number of items.
var counter = [
[]
]; // Radix sort Array container to hold arrays from 0th digit to 9th digits
function radixSortLSD(array) {
var max = 0,
mod = 10,
dev = 1; //max
for (var i = 0; i < array.length; i++) {
if (array[i] > max) {
max = array[i];
}
}
// determine the large item length
var maxDigitLength = (max + '').length;
for (var i = 0; i < maxDigitLength; i++, dev *= 10, mod *= 10) {
for (var j = 0; j < array.length; j++) {
var bucket = Math.floor((array[j] % mod) / dev); // Formula to get the significant digit
if (counter[bucket] == undefined) {
counter[bucket] = [];
}
counter[bucket].push(array[j]);
}
var pos = 0;
for (var j = 0; j < counter.length; j++) {
var value = undefined;
if (counter[j] != undefined) {
while ((value = counter[j].shift()) != undefined) {
array[pos++] = value;
}
}
}
}
console.log("ARRAY: " + array);
};
var sampleArray = [1, 121, 99553435535353534, 345, 0];
radixSortLSD(sampleArray);function radixSort(arr) {
const base = 10;
let divider = 1;
let maxVal = Number.NEGATIVE_INFINITY;
while (divider === 1 || divider <= maxVal) {
const buckets = [...Array(10)].map(() => []);
for (let val of arr) {
buckets[Math.floor((val / divider) % base)].push(val);
maxVal = val > maxVal ? val : maxVal;
}
arr = [].concat(...buckets);
divider *= base;
}
return arr;
}
Disclaimer: it works only with positive integers.
Math.max as it uses a lot of resources for very large arrays.Doing a LSD radix sort via bitwise operations could go something like this:
const initialMask = 0b1111;
const bits = 4;
const getBuckets = () => Array.from(
{ length: (2 * initialMask) + 1 },
() => [],
);
function radixSort(array) {
let max = 0;
array.forEach(n => {
const abs = Math.abs(n);
if (abs > max) max = abs;
});
if (max >= 0x80000000) {
throw new Error('cannot perform bitwise operations on numbers >= 0x80000000');
}
for (
let mask = initialMask,
shifted = 0,
buckets = getBuckets();
true;
mask = (mask << bits),
shifted = (shifted + bits),
buckets = getBuckets()
) {
array.forEach(n => {
const digit = mask & Math.abs(n);
const bucket = (Math.sign(n) * (digit >> shifted)) + initialMask;
buckets[bucket].push(n);
});
let i = 0;
buckets.forEach(bucket => bucket.forEach(n => {
array[i] = n;
i += 1;
}));
if ((max ^ mask) <= mask) break;
}
}
const getArray = () => Array.from(
{ length: 1e6 },
() => Math.floor(Math.random() * 0x80000000) * Math.sign(Math.random() - 0.5),
);
const isSorted = array => {
for (let i = 1; i < array.length; i += 1) {
if (array[i - 1] > array[i]) return false;
}
return true;
}
const radixArray = getArray();
const nativeArray = radixArray.slice();
const radixStart = +new Date();
radixSort(radixArray);
const radixEnd = +new Date();
const nativeStart = +new Date();
nativeArray.sort();
const nativeEnd = +new Date();
document.write(`
<dl>
<dt>Sorted array in</dt>
<dd>${radixEnd - radixStart}ms</dd>
<dt>Properly sorted</dt>
<dd>${isSorted(radixArray)}</dd>
<dt>Sorted with Array.prototype.sort in</dt>
<dd>${nativeEnd - nativeStart}ms</dd>
</dl>
`);What's going on here?
We're sorting by base 8 (0b1111 helps conceptualize the bitwise operations).
We create 0b1111 * 2 + 1 buckets, which is the number of items in the set [-0b1111 … 0b1111]
We use the "mask" to get each base 8 digit of a given number, e.g.
if n = 0b101000101010, n & 0b1111 gives us 0b1010, which is the first base 8 digit of n.
For each iteration, we get n & 0b11110000, then n & 0b111100000000, which isolates each successive base 8 digit.
For n & 0b11110000, we get 0b00100000, from which we want 0b0010, so we perform a right shift by 4 bits. The next iteration would be shifted by 8 bits, so on and so forth.
To account for negative values, we're basically performing two radix sorts simultaneously: the negative values are sorted in reverse, and the positive values are sorted in normal order. If the digit is negative, we say a digit of 7 should be at 0, 6 at 1, 5 at 2, etc.
If it is positive, we say a radix of 7 should be at index 14, 6 at 13, etc.
The check at the end - (max ^ mask) <= mask - determines if or not the mask has taken the most significant digit of the maximum value. If it has, the array is sorted.
Of course, radix sort only can work with integers.
If you need to use numbers larger than 0x80000000, you could do an implementation with strings.
I encountered radix sort in CRLS 3rd edition section 8.3
The book provided the arcane origins of radix sort. It described the MSD version as antiquated and tricky. It also advised the implementation of the LSD.
Here I provide an implementation of radix sort using this technique.
Let's start by the pseudo-code:
/**
* @param k: the max of input, used to create a range for our buckets
* @param exp: 1, 10, 100, 1000, ... used to calculate the nth digit
*/
Array.prototype.countingSort = function (k, exp) {
/* eslint consistent-this:0 */
/* self of course refers to this array */
const self = this;
/**
* let's say the this[i] = 123, if exp is 100 returns 1, if exp 10 returns 2, if exp is 1 returns 3
* @param i
* @returns {*}
*/
function index(i) {
if (exp)
return Math.floor(self[i] / exp) % 10;
return i;
}
const LENGTH = this.length;
/* create an array of zeroes */
let C = Array.apply(null, new Array(k)).map(() => 0);
let B = [];
for (let i = 0; i < LENGTH; i++)
C[index(i)]++;
for (let i = 1; i < k; i++)
C[i] += C[i - 1];
for (let i = LENGTH - 1; i >= 0; i--) {
B[--C[index(i)]] = this[i];
}
B.forEach((e, i) => {
self[i] = e
});
}
And that's the only tricky part, the rest is very simple
Array.prototype.radixSort = function () {
const MAX = Math.max.apply(null, this);
/* let's say the max is 1926, we should only use exponents 1, 10, 100, 1000 */
for (let exp = 1; MAX / exp > 1; exp *= 10) {
this.countingSort(10, exp);
}
}
Now here is a how you can test this method
let a = [589, 111, 777, 65, 124, 852, 345, 888, 553, 654, 549, 448, 222, 165];
a.radixSort()
console.log(a);
Finally, as mentionned in the book, this particular algorithm works only because counting-sort is an in-place sorting algorithm, which means that if two elements tie, their order of occurence in the input array is preserved.
I'm sure all these answers work, but I believe heavily in factoring to explain what's going on under the hood. Thus, here is the answer with helper methods:
// helper
function getDigit(num, place) {
return Math.floor(Math.abs(num) / Math.pow(10, place)) % 10;
}
// helper
function digitCount(num) {
if (num === 0) {
return 1;
}
return Math.floor(Math.log10(Math.abs(num))) + 1;
}
// helper
function mostDigits(nums) {
let max = 0;
for (let num of nums) {
max = Math.max(max, digitCount(num));
}
return max;
}
function radixSort(nums) {
let maxDigits = mostDigits(nums);
for (let k = 0; k < maxDigits; k++) {
let buckets = Array.from({length: 10}, () => []);
for (let num of nums) {
let digit = getDigit(num, k);
buckets[digit].push(num);
}
nums = [].concat(...buckets);
}
return nums;
}
My Implementation
// get the digits in the number by index
const getDigit = (num, index) => {
return Math.floor(Math.abs(num) / Math.pow(10, index)) % 10;
}
// get the number of digits in a number
const getNumberOfDigits = (num) => {
if(num === 0) return 1;
return Math.floor(Math.log10(Math.abs(num))) + 1;
}
// get the max Number of digits in arr
const getMaxNumOfDigits = (arr) => {
let max = 0;
for(let item of arr) {
max = Math.max(max, getNumberOfDigits(item))
}
return max;
}
// sorting the numbers
const radixSort = (arr) => {
let maxIteration = getMaxNumOfDigits(arr),
buckets;
for (let i = 0; i < maxIteration; i++) {
// set bucket to arr of 10 empty sub arrs
buckets = Array.from({length: 10}, () => []);
for(let item of arr) {
// put the number in the right bucket position
buckets[getDigit(item, i)].push(item);
}
// re-collect from the buckets
arr = [].concat(...buckets);
}
return arr;
}
// get the digits in the number by index
const getDigit = (num, index) => {
return Math.floor(Math.abs(num) / Math.pow(10, index)) % 10;
}
// get the number of digits in a number
const getNumberOfDigits = (num) => {
if(num === 0) return 1;
return Math.floor(Math.log10(Math.abs(num))) + 1;
}
// get the max Number of digits in arr
const getMaxNumOfDigits = (arr) => {
let max = 0;
for(let item of arr) {
max = Math.max(max, getNumberOfDigits(item))
}
return max;
}
// sorting the numbers
const radixSort = (arr) => {
let maxIteration = getMaxNumOfDigits(arr),
buckets;
for (let i = 0; i < maxIteration; i++) {
// set bucket to arr of 10 empty sub arrs
buckets = Array.from({length: 10}, () => []);
for(let item of arr) {
// put the number in the right bucket position
buckets[getDigit(item, i)].push(item);
}
// re-collect from the buckets
arr = [].concat(...buckets);
}
return arr;
}
radixSort([9, 212, 55, 19, 111, 3])
console.log(radixSort([9, 212, 55, 19, 111, 3]))