How to implement Radix Sort

My favorite non-comparison sorting algorithm!

Post graduation, I have been going in on ensuring my algorithm knowledge is on point. It should come to no surprise (if you’re a developer) that having data structure and algorithm knowledge may be crucial to your success at landing a job. While many companies are fighting against this, there is nothing wrong with strengthening your problem solving and critical thinking skills. After all, that’s your job as a developer!

What is Radix Sort?

I recently stumbled upon radix sort and it’s been a new favorite, greatly due to the fact it’s a fun algorithm to visualize and work on. It differs from other sorting algorithms (quick sort, merge sort, etc) because it doesn’t actively compare arrays of elements, and instead distributes elements of an array into “buckets” dependent on each digit of an element.

Each “bucket” will be represented by a specific number 1–9, and the elements will get sorted into these buckets by grouping single digits of the same place value in the element. Let’s get started by visualizing an array of numbers.

[14, 495, 12, 7, 192, 38, 98]

First, you should note that your sort will go through 3 iterations, and we know this due to the fact our largest number (495) has three digits.

Second, we want to visualize each place value getting sorted based on the value of that specific element.

[14, 495, 12, 7, 192, 38, 98] 
// first bucket sort
        12                      38
        192    14  495      7   98 
0.  1.  2.  3.  4.  5.  6.  7.  8.  9.

[14, 495, 12, 7, 192, 38, 98]
//second bucket sort (tens place)
7   12  14  38                     98
                                   192
                                   495 
0.  1.  2.  3.  4.  5.  6.  7.  8.  9.
*7 is in the 0 spot because it does not have a tens digit

[14, 495, 12, 7, 192, 38, 98]
//third bucket sort (hundreds place)
7
12
14
38
98 192          495
0.  1.  2.  3.  4.  5.  6.  7.  8.  9.
ALL DONE!

As you can see, as we progress through the digits, our buckets begin to fill up in order of value of each element.

The Code

In order to successfully implement an algorithm, it’s important to think in terms of pseudocode. We need:

• the # of digits in the larger number of the array, we can do this by looping through
• create a bucket for each digit (0–9) and place each element in the bucket corresponding with the value
• return the UPDATED array (no creating new arrays here!)

Like any coding problem, whether a real world implementation or an algo problem, we can create helper methods to assist us in breaking down the steps. Looking back at the pseudocode, we can make a few helper methods:

function digitPlace(num, index) {
     return Math.floor(Math.abs(num) / Math.pow(10, index))  % 10
}
// this will return the digit at the specific place value we are in 
function digitCount(num) {
   if (num === 0) return 1;
   return Math.floor(Math.log10(Math.abs(num)) + 1
}
// write a recursive method that tells you how many digits are in a number, and how many times we will need to sort into the buckets. 
function mostDigits(arr) {
    let maximum = 0;
    for (let i = 0; i < arr.length; i++) {
       maximum = Math.max(maximum, digitCount(arr[i]));
    }
  return maximum;
}
// given the array of #s, will return the number of digits in the largest #s in the array

Now that we have all the pseudocode and helper methods out of the way, it’s time to start writing our radixSort function! It will take in an initial array of numbers. Using our helper methods, we will set a variable maxDigCount equal to our helper recursive method of mostDigits. We will then set up 2 loops: one to iterate through the mostDigits array and help the function determine the largest number of digits, and another loop to create buckets for each digit and place each element into the corresponding digit dependent on the jth digit.

function radixSort(arr) {
   let maxDigCount = mostDigits(arr);
   for (j = 0; j < maximum; k++) {
     let buckets = Array.from({length:10}, () => []);
//Array.from() allows you to create a new "lazy" array 
//We added the length of 10 in order to create the buckets from 0-9, instead of setting the array to say [0, 1, 2...9]
     for (let i = 0; i < arr.length; i++) {
       let dig = digitPlace(arr[i], k);
       buckets[dig].push(arr[i]):
       //here is where we are pushing each element into its bucket
    }
   arr = [].concat(...buckets);
   // this syntax is using the ES6 spread operator to concatenate all of the buckets into the initial array of numbers
   }
return arr

Big O Advantages

One of the main advantages of radix sort is its time complexity, which is O(kn). N represents the amount of elements and k represents the number of digits within the array. This is better than the majority of the popular sorting algorithms, where the time complexity is on average O (n log n). The space complexity of radix sort is O (n + k)!

I hope you enjoyed my breakdown of radix sort :) Until next time!