Radix sort algorithm in Javascript

Learn what is radix sort algorithm and how to implement it in Javascript.

List of sorting algorithms

• Bubble sort algorithm in javascript
• Insertion sort algorithm in javascript
• Selection sort in javascript
• Merge sort in javascript
• Quick sort in javascript
• Counting sort in javascript
• Bucket sort in javascript
• Shell sort in javascript
• Heap sort in javascript

What is radix sort?

Radix sort is an non-comparison based sorting algorithm. It uses radix of the elements to distribute them in buckets to avoid the comparison.

It sorts the elements by first grouping or distributing them in buckets on the individual digits of the same place value.

For example suppose we have an array of 10 elements. First, we will sort elements based on the value of the unit place. Then, we will sort elements based on the value of the tenth place. This process goes on until the last significant place.

Input:
[121, 432, 564, 23, 1, 45, 788]

Output:
[1, 23, 45, 121, 432, 564, 788]

As it breaks the elements at it’s place after every cycle, radix sort can only be performed on integers.

You should be familiar with the counting sort before learning radix sort because it uses counting sort as an intermediate sort.

Below image shows the working of radix sort on an array of elements.

How radix sort works?

1. First find the largest element from the array i.e max and let d be the number of digits in the max, because we have to cycle through each significant places of the largest number.

2. Now, go through each significant place one by one and use any stable sorting technique to sort the digits at each significant place. I have used counting sort for this as it is an integer based sorting algorithm.

radixSort(array)
  d <- maximum number of digits in the largest element
  create d buckets of size 0-9
  for i <- 0 to d
    sort the elements according to ith place digits using countingSort

countingSort(array, d)
  max <- find largest element among dth place elements
  initialize count array with all zeros
  for j <- 0 to size
    find the total count of each unique digit in dth place of elements and
    store the count at jth index in count array
  for i <- 1 to max
    find the cumulative sum and store it in count array itself
  for j <- size down to 1
    restore the elements to array
    decrease count of each element restored by 1

---

Radix sort algorithm on array of positive integers.

As we are going to use the counting sort as an intermediate sort, we will have to modify it a little, we will receive place as an input in each cycle and use this to pull out digits at that place for each element in the array and sort the elements accordingly.

const countingSort = (arr, size, place) => {
  
  let output = new Array(size + 1).fill(0);
  let max = Math.max(...arr);
  
  let freq = new Array(max + 1).fill(0);
  
  // Calculate count of elements
  for (let i = 0; i < size; i++){
      const num = Math.floor(arr[i] / place) % 10;
      freq[num]++;
  }
  
  // Calculate cummulative count
  for (let i = 1; i < 10; i++){
      freq[i] += freq[i - 1];
  }

  // Place the elements in sorted order
  for (let i = size - 1; i >= 0; i--) {
      const num = Math.floor(arr[i] / place) % 10;
      output[freq[num] - 1] = arr[i];
      freq[num]--;
  }
  
  //Copy the output array
  for (let i = 0; i < size; i++){
    arr[i] = output[i];
  }
}

const radixSort = (arr, size = arr.length) => {
  //Get the max element
  let max = Math.max(...arr);
  
  //Sort the array using counting sort
  for(let i = 1; parseInt(max / i) > 0; i *= 10){
    countingSort(arr, size, i);
  }
}

Input:
const arr = [121, 432, 564, 23, 1, 45, 788];
radixSort(arr);
console.log(arr);

Output:
[1, 23, 45, 121, 432, 564, 788]

---

Radix sort algorithm on array of negative integers in Javascript

const countingSortNegative = (arr, n, place) => {
  let max = Math.max(...arr);
  let min = Math.min(...arr);
  let range = max - min + 1;
  let count = new Array(range).fill(0);
  let output = new Array(n).fill(0);
  
  //Store the frequency
  for (let i = 0; i < n; i++) {
    const num = Math.floor(arr[i] / place) % 10;
    count[num - min]++; 
  } 
 
  //Accumulate the frequency
  for (let i = 1; i < count.length; i++) { 
    count[i] += count[i - 1]; 
  } 
  
  //Sort based on frequency
  for (let i = n - 1; i >= 0; i--) { 
    const num = Math.floor(arr[i] / place) % 10;
    output[count[num - min] - 1] = arr[i]; 
    count[num - min]--; 
  } 
  
  //Copy the output array
  for (let i = 0; i < n; i++){
    arr[i] = output[i];
  }
}

const radixSort = (arr, size = arr.length) => {
  //Get the max element
  let max = Math.max(...arr);
  
  //Sort the array using counting sort
  for(let i = 1; parseInt(max / i) > 0; i *= 10){
    countingSortNegative(arr, size, i);
  }
}

Input:
const arr = [121, -432, 564, 23, -1, 45, 788];
radixSort(arr);
console.log(arr);

Output:
[-432, -1, 23, 45, 121, 564, 788]

---

Time complexity

As radix sort is a non-comparison based sorting algorithm it has certain advantages while sorting the integers.

Counting sort has the time complexity of (n+k) where n is the size of the array and k is the max element in the array.

In the radix sort, we use counting sort for each digit of the max element in the array. Let's call this digits as d, so the time complexity is O(d * (n + k)).

Thus, radix sort has linear time complexity which is better than O(nlog n) of comparative sorting algorithms.

If we take very large digit numbers or the number of other bases like 32-bit and 64-bit numbers then it can perform in linear time however the intermediate sort takes large space.

This makes radix sort space inefficient. This is the reason why this sort is not used in software libraries.

---

Space complexity

The space complexity of Radix sort is O(max). Larger the range of elements, larger is the space complexity.