Radix Sort

Today, we'll discuss one of the fastest sorting algorithms. However, there's beauty here for sure but no magic it only works for numbers.

Theory

Numbers only? Yes, because our algorithm relies solely on numbers. We will use each digit of each number to place the number into the corresponding bucket, ranging from 0 to 9. For each iteration, we will return an array that is partially sorted until we've looped over every digit.

But what if there is no value for the current digit? In that case, it will go to the first bucket (0), meaning it was previously sorted.

Implementation

To make this more manageable, we will create some utility functions.

The first one will be getDigit which takes two parameters: the number and the index of the digit we are examining. For example, getDigit(193, 2) returns 1.

We have two ways of doing this:

• Convert the number parameter to a string. However, since strings are read from left to right and numbers work the other way around, we need some additional logic.
• Use a mathematical approach commonly found on platforms like Stack Overflow:

function getDigit(number, digit) {   
  return Math.floor(number / Math.pow(10, digit)) % 10;
};

Here, we divide by the nth place (for example, if the digit parameter is 2, we divide by 100), then we floor the result and apply modulo 10 to find out how many times 10 fits into the resulting number.

Next, we need to determine where to stop iterating or the maximum number of digits in the provided array:

function getMaxDigits(arr) {   
  let max_digits = 0;   
  for (let num of arr) {      
    max_digits = Math.max((""+num).length, max_digits);   
  }   
 return max_digits;
};

getMaxDigits([1234, 5, 67]) // 4

Explanation:

This is quite straightforward. We define a maxDigits variable starting at 0 and then we loop over each provided number, reassigning our variable to the maximum value between the current maxDigits and the length of the number.

Finally, we create our radixSort function, which essentially puts our previously defined functions to good use:

function radixSort(arr) {  
 const max_digits = getMaxDigits(arr);   
 for (let i = 0; i < max_digits; i++) {      
   let buckets = Array.from({length: 10}, () => 
 []);
   for (let j = 0; j < arr.length; j++) {         
     buckets[getDigit(arr[j], i)].push(arr[j]);      
   };      
   arr = [].concat(...buckets);   
}   
return arr;
};

As you can see, once you have all your utility functions, it's pretty straightforward:

• Determine how many loops are necessary using our getMaxDigits function. For example, with the array 1, 23, 456, 7890, we will loop 4 times.
• For each iteration, we will create a bucket to store digits from 0 to 9.
• Loop over the provided array for the maximum number of digits, placing each value in the bucket according to the digit we are currently examining. For the first digit in the array 1, 23, 456, 7890, we look at the values 1, 3, 6, 0 etc..
• Reassign our parameter arr by extracting each value in their current order from the buckets.

So, after the first iteration, our arr parameter will look like this: 7890, 1, 23, 456. After the second iteration, our arr would look like this: 1, 23, 456, 7890, which already makes more sense.

Performance considerations

As you can see, this algorithm is straightforward and fast. Yes, it is almost O(n). Why almost?

Well, because we have a loop inside a loop, which should mean O(n²). However, since the outer loop's length is based on the maximum digits, it usually is a rather small number. By small, I mean less than 1000. So, we generally agree that it should be O(nk), where n is the number of items in the provided parameter and k is the number of digits of the largest number.

Here are some key points to consider:

• Worst-case scenario: O(nk) In the worst-case scenario, where the numbers are in reverse order, we only have to loop over every element k number of times, where k is the maximum number of digits
• Best-case scenario: O(nk) In the best-case scenario, where the array is already sorted, radix sort will still have to loop over every element k number of times, where k is the maximum number of digits.
• Average-case scenario: O(nk) On average, radix sort requires the same number of iterations, resulting in an average time complexity of O(nk), which makes it a solid option for sorting numbers.

Practical Use Cases

Radix sort is particularly suitable for sorting arrays of numbers.

Conclusion

Radix sort stands out as an exceptionally efficient algorithm for sorting numbers, often outperforming many other sorting algorithms in terms of performance. Its unique approach of leveraging individual digits to sort numbers makes it particularly efficient for large datasets where numerical sorting is required. However, what makes it so efficient also makes so specialized, only applicable to numerical data, which limits its versatility compared to more general-purpose sorting algorithms.

Happy coding!