Javascript Radix Sort

Question

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.

Answer 1

For those who are afraid of using many for loops thinking it impacts runtime here is the TS version with minimum loops, handles negative values. But. Loops do not increment runtime by themselves, refer to the Asymptotic Running Time of Algorithms - it is not just counting the nested loops.

Code explanation:

1. While loop - iterates over each digit from right to left (LSD) by dividing the numbers by powers of 10 (1, 10, 100 etc). It terminates when we get 0 for all the elements in the array when dividing by mod. So you cannot get rid of it. If you do radix sort - you need to traverse all the digits.
2. Nested for loop - traverses all the elements of the array placing the original num to the proper bucket (negative or positive). It is also the necessary loop - no way to get rid of it, how are we going to check the elements, right?
3. Sorted array returned explicitly without modifying the original nums array. Special for those who are afraid of extra for lȏⴰ︎ȏps :D

function radixSort(nums: number[]): number[] {
  let positiveBuckets: number[][]
  let negativeBuckets: number[][]

  let allNumsProcessed = false
  let divider = 1

  while (!allNumsProcessed) {
    allNumsProcessed = true

    positiveBuckets = []
    negativeBuckets = []
    
    for (let i = 0; i < nums.length; i++) {
      let digit = Math.trunc(nums[i] / divider) % 10
      let isNegative = false
      
      if (nums[i] < 0) {
        digit *= -1
        isNegative = true
      }

      const buckets = isNegative ? negativeBuckets : positiveBuckets

      if (!buckets[digit])
        buckets[digit] = []

      buckets[digit].push(nums[i])

      if (Math.trunc(nums[i] / (divider * 10)) !== 0)
        allNumsProcessed = false
    }
    
    nums = [...negativeBuckets.reverse().flat(), ...positiveBuckets.flat()]
    divider *= 10
  }

  return nums
}

Answer 2

I wrote an LSD Radix Sorter implementation to sort integers and floating point numbers. It uses a bitmask to reduce the number of iterations.

Compared to Joseph Nields Answer is twice as fast when testing with an array of 1000000 numbers and a range of -0x80000000 to 0x80000000

https://github.com/aldo-gutierrez/bitmasksorterJS

Answer 3

Radix Sort (LSD)

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.

• For mixed negative & positive integers check this version.
• I avoid using Math.max as it uses a lot of resources for very large arrays.

Answer 4

User Jason Leonhard resurrected this old question to look for new solutions. He seems to think that all the loops in the various answers are a performance problem. While I doubt that's true, here's a version which at least hides the explicit loops behind array methods and a recursive call:

// problems with Math.max for large parameter lists
const maximum = (ns) => ns .reduce ((m, n) => n > m ? n : m, -Infinity)

const radixSort = (ns, max = maximum (ns), divisor = 1) =>
  divisor < max
    ? radixSort (ns .reduce (
        (buckets, n) => ((buckets [(~~ (n / divisor)) % 10] .push (n)), buckets),
        [... Array (10)] .map (() => []) 
      ) .flat (), max , divisor * 10)
    : ns

console .log (radixSort ([5, 3, 88, 235, 65, 23, 4632, 234]))
console .log (radixSort ([589, 111, 777, 65, 124, 852, 345, 888, 553, 654, 549, 448, 222, 165]))

.as-console-wrapper {max-height: 100% !important; top: 0}

This one only works with positive integers. There are things we could do to optimize this a bit. We could inline the call to maximum. We could replace [... Array (10)] .map (() => []) with [[], [], [], [], [], [], [], [], [], []]. Those would reduce clock time a tiny bit, but would not change the algorithmic complexity.

As with many other answers here, it looks like the algorithmic complexity is O (n * d) where n is the number of elements to sort, and d is the number of digits in the largest element. The actual speed is probably less than that of the answer from Lior Elrom, since it exposes the same algorithm but uses recursive function calls instead of a while loop. Or perhaps not, since it only finds the largest value once up front, instead of on every iteration like that answer. But the important point is that without benchmarking, we really don't know which of these is the fastest, or for how many number / what highest number of digits any one of these is faster than another.

Answer 5

I'm sure all these answers work, but I believe heavily in refactoring 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;
}

Answer 6

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.log(testArray);          

Answer 7

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;
    }


radixSort([9, 212, 55, 19, 111, 3])


console.log(radixSort([9, 212, 55, 19, 111, 3]))

Answer 8

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.

Answer 9

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);

Answer 10

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:

• Uint32Array
• Int32Array
• Float32Array
• Uint16Array
• Int16Array
• Uint8Array
• Int8Array
• Any plain array where you know all values fit one of these criteria

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

Answer 11

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.

Answer 12

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));