Radix Sort

Having gone through the Quadratic Sorting Algorithms (Bubble Sort, Selection Sort, Insertion Sort), as well as Merge Sort and most recently Quicksort, I want to do a blog post on Radix Sort and then probably take a rest on sorting algorithms for a little while. These have been fun, and I've learned a ton, but I want to put energy and focus into some other topics.

Review: Comparison Sorts

As a bit of review, Bubble Sort, Selection Sort, Insertion Sort, Merge Sort, and Quicksort all have something in common with their approaches: they directly compare two values at any given step in their process. Because of this, they are commonly grouped together and referred to as Comparison Sorts.

You might also remember from those previous posts that these algorithms have the following Time Complexities:

• Bubble Sort: O(n²)
• Insertion Sort: O(n²)
• Selection Sort: O(n²)
• Merge Sort: O(n log n)
• Quicksort: O(n log n)

So clearly the Quadratic Sorting Algorithms aren't very efficient, and Merge Sort and Quicksort are a little more efficient. However, to achieve even greater efficiency we need to step out of direct comparisons. Radix Sort does just that.

How Does Radix Sort Work?

Radix Sort is an example of an Integer Sort, which doesn't directly compare two numbers. Instead, it exploits the fact that information about the size of the number is encoded in the number of digits. Largely speaking, if a number has more digits that means it's a bigger number.

Radix Sort works by creating buckets that correspond to each of the single digits between 0 and 9 (0, 1, 2, 3, 4, 5, 6, 7, 8, and 9). It then looks at the same place in every number, and places that number into the bucket that corresponds to the digit at the place where it is looking. If our numbers are [101, 1, 202, 12, 23], and we're looking at the first place, then 101 and 1 go into the 1 bucket. 202 and 12 go into the 2 bucket, and 23 goes into the 3 bucket.

After placing the numbers into their buckets based on the place that the algorithm is looking at, the algorithm then rebuilds the list in the order they went into each bucket. It then looks at the next place over in each digit. 101 gets sorted into 0. 1 also gets sorted into 0 (it pads out non-existent places with 0). 202 also gets sorted into 0. 12 gets sorted into the 1 bucket. Finally, 23 gets sorted into the 2 bucket. It then reconstructs the list. It does this all the way through the longest number available, in this case three rounds of bucket/reconstructing the list (since the longest numbers, 101 and 202 have three digits each). A sorted list naturally results from the order in which the numbers are split into buckets and then reconstructed into the list.

Radix Sort Step by Step

As always, describing these algorithms is tricky and it may be easier to break down each step very explicitly.

Let's say this is our list: [1556, 4, 3556, 593, 408, 4386, 902, 7, 8157, 86, 9637, 29].

First Bucket Round

The first thing we do is create 10 buckets: 0, 1, 2, 3, and so on all the way until 9.

Now, for every number in our list, we're going to look at the digit that is in the first place (farthest to the right), and place each number into the bucket that corresponds to the digit that is in that first place.

For example:

• 1556 goes into the 6 bucket
• 4 goes into the 4 bucket
• 3556 goes into the 6 bucket

and so on. Here is the result of what I'll call our First Bucket Round:

First List Reconstruction

Now we reconstruct the list, going bucket by bucket, and putting numbers into the list in the order in which they went into the bucket.

For example:

• 902 comes out first
• 593 comes next
• 4 comes next
• 1556 comes next
• 3556 comes next

and so on. Here is the result of what I'll call the First List Reconstruction:

[902, 593, 4, 1556, 3556, 4386, 86, 7, 8157, 9637, 408, 29]

Second Bucket Round

With our newly ordered list in hand, we split the numbers up into their buckets again, but this time looking at the next place over, one place to the left of where we previously looked. If a number does not have a digit there, we assume it as a 0 and place the number into the 0 bucket.

For example:

• 902 goes into the 0 bucket
• 593 goes into the 9 bucket
• 4 goes into the 0 bucket
• 1556 goes into the 5 bucket

and so on. Here is the result of our Second Bucket Round:

Second List Reconstruction

Now we reconstruct the list again, going bucket by bucket and in the order that each number went into their buckets. Here is the result of our Second List Reconstruction:

[902, 4, 7, 408, 29, 9637, 1556, 3556, 8157, 4386, 86, 593]

Third Bucket Round

With our newly reordered list in hand, we move onto the next (third from the right) place in each number and place them into their buckets again. Again if the number doesn't have a digit in that place, we assume a 0 and place it into the 0 bucket.

Here is the result of our Third Bucket Round:

Third List Reconstruction

Now we reconstruct the list again, bucket by bucket, in the order in which each number went into its bucket. Here is the result of our Third List Reconstruction:

[4, 7, 29, 86, 8157, 4386, 408, 1556, 3556, 593, 9637, 902]

Fourth Bucket Round

With our newly reordered list in hand, we move onto the next (fourth from the right) place in each number and place them into buckets once more. Again if the number doesn't have a digit in that place, we assume a 0 and place it into the 0 bucket.

Here is the result of our Fourth Bucket Round:

Fourth List Reconstruction

Now we reconstruct the list again, bucket by bucket, in the order in which each number went into its bucket. Here is the result of our Fourth List Reconstruction:

[4, 7, 29, 86, 408, 593, 902, 1556, 3556, 4386, 8157, 9637]

And just like that we have a list that's sorted! It's kind of magical and really cool to see something like this come together, but let's write some code that makes it happen.

Helper Functions

We're going to need three helper functions that make the above process work:

• getDigit, which accepts a number and a place, and returns the value at that place in the number
• digitCount, which accepts a number and returns the number of digits in that number
• mostDigits, which accepts an array and returns the number of digits in the largest number(s) in the array

These three functions utilize a handful of methods taken from JavaScript's built-in Math object. I won't pretend that I understand what all of them do exactly. I've provided a brief explanation for most of these Math methods as well as links to their definitions on MDN.

getDigit Helper Function

The getDigit function accepts a number, num, and a number, place, and returns the value at place in num.

getDigit(num, place);

Examples

• getDigit(12345, 0); returns 5
• getDigit(12345, 1); returns 4
• getDigit(12345, 2); returns 3
• getDigit(12345, 3); returns 2
• getDigit(12345, 4); returns 1
• getDigit(12345, 5); returns 0

getDigit Implementation

function getDigit(num, place) {
  return Math.floor(Math.abs(num) / Math.pow(10, place)) % 10;
}

This function uses three JavaScript Math functions:

• Math.floor() - which returns the largest integer less than or equal to a given number
• Math.abs() - which returns the absolute value of a number
• Math.pow() - returns the value of the given base taken to the power of the given exponent

digitCount Helper Function

The digitCount function accepts a number, num, and returns the number of digits in num.

digitCount(num);

Examples

• digitCount(1); returns 1
• digitCount(25); returns 2
• digitCount(314); returns 3

digitCount Implementation

function digitCount(num) {
  if (num === 0) {
    return 1;
  } else {
    return Math.floor(Math.log10(Math.abs(num))) + 1;
  }
}

This function uses three JavaScript Math functions:

• Math.floor() - which returns the largest integer less than or equal to a given number
• Math.log10() - which returns the base 10 logarithm of a given number
• Math.abs() - which returns the absolute value of a number

mostDigits Helper Function

The mostDigits function accepts an array, arr and returns the number of digits in the largest number(s) in the list.

mostDigits(arr);

mostdigits Implementation

Examples

• mostDigits([1, 2, 3]); returns 1
• mostDigits([1, 2, 33]); returns 2
• mostDigits([1, 2, 7654321]); returns 7

function mostDigits(arr) {
  let maxDigits = 0;
  for (let i = 0; i < arr.length; i++) {
    maxDigits = Math.max(maxDigits, digitCount(arr[i]));
  }
  return maxDigits;
}

This function creates a variable named maxDigits, initially set to the value of 0.

It then loops through each number in the array, and uses digitCount() on each array item to determine how many digits are in each array item. It uses Math.max() to compare the result of digitCount and if digitCount is greater, reassigns maxDigits to the value of digitCount.

Radix Sort Implementation

function getDigit(num, place) {
  return Math.floor(Math.abs(num) / Math.pow(10, place)) % 10;
}

function digitCount(num) {
  if (num === 0) {
    return 1;
  }
  return Math.floor(Math.log10(Math.abs(num))) + 1;
}

function mostDigits(arr) {
  let maxDigits = 0;
  for (let i = 0; i < arr.length; i++) {
    maxDigits = Math.max(maxDigits, digitCount(arr[i]));
  }
  return maxDigits;
}

function radixSort(arr) {
  let maxDigitsCount = mostDigits(arr);
  for (let k = 0; k < maxDigitsCount; k++) {
    let digitBuckets = Array.from({ length: 10 }, () => []);
    for (let i = 0; i < arr.length; i++) {
      let digit = getDigit(arr[i], k);
      digitBuckets[digit].push(arr[i]);
    }
    arr = [].concat(...digitBuckets);
  }
  return arr;
}

The last thing to do is to create our radixSort function, which accepts our array of numbers, arr, and then uses the three helper functions to do the bucket sorting and list mutation operations.

The first thing we do is use mostDigits() to determine how many rounds of bucket sorting/list mutation need to happen, and save that into a variable named maxDigitsCount. This is based on how many digits are in the largest number in the array. If the largest number is 126, which has 3 digits, then maxDigitsCount would return 3. If the largest number is 7654321, which has 7 digits, then maxDigitsCount would return 7.

The next thing we do is start a loop that counts up from 0 through the value of maxDigitsCount. Each iteration of the loop will do two things:

1. Sort the array items into buckets based on the place in the number we're looking at
2. Re-sort the list based on their order after bucket sorting

The first thing we do inside of the loop is create an array of ten empty arrays. I like to do this with the Array.from() method, which I pass an object with a length property – the value of this length property will be the number of items in this empty array – as well as a callback function, which returns the value that we want to populate in each item of the new array. In this case that's just an empty array. I save this array of sub-arrays into a variable named digitBuckets.

So let digitBuckets = Array.from({ length: 10 }, () => []); gives me an array that looks like:

[
  [],
  [],
  [],
  [],
  [],
  [],
  [],
  [],
  [],
  [],
]

The array has ten sub-arrays, and each of these sub-arrays are indexed 0 through 9. These will be the buckets that we put the various numbers into.

The next thing we do inside of our loop is to start another loop that iterates through the array, finds the digit in the at looking in each number, and uses that digit to place the number into the proper digitBuckets bucket.

That is what the following loop does:

for (let i = 0; i < arr.length; i++) {
  let digit = getDigit(arr[i], k);
  digitBuckets[digit].push(arr[i]);
}

Once the inner loop stops running then the numbers are sorted into their various buckets. At this point we need to reconstruct the list, bucket by bucket, in the order in which they were put into their buckets. We can do this by creating a new, empty array, and then .concat() each bucket by spreading the contents of each bucket into the new empty array.

This is what the following line accomplishes:

arr = [].concat(...digitBuckets);

Once the outer loop stops running, arr will have been sorted in place, and we simply need to return arr.

Radix Sort Big O

In all cases, we achieve a Time Complexity of O(nk), where n is the number of items in the array and k is the number of digits in the longest array item. Remember that if the longest number in the array is 7654321, which has 7 digits, then k is 7 and the algorithm will need to do 7 steps where it sorts the numbers into buckets and reconstructs the list.

As for Space Complexity, we are sorting the array in place, which gives us O(n) memory, but also creating that extra digitBuckets array for each of the k iterations of the loop, giving us an extra k demand for memory. Therefore Space Complexity is O(n + k).