While preparing for a technical interview for a software developer, coding engineer, software engineer, or any other software engineering role, in-depth knowledge of sorting algorithms comes in handy. These can help you crack many coding problems.

We’ll brush up on one of these sorting algorithms in this article — the radix sort. We’ll discuss:

• What Is Radix Sort?
• Applications of Radix Sort
• How Does Radix Sort Work?
• Radix Sort Algorithm
• Radix Sort Pseudocode
• Radix Sort Code
• Radix Sort Complexities
• Strengths and Weaknesses of Radix Sort
• FAQs on Radix Sort

What Is Radix Sort? 

Radix sort is a non-comparison-based sorting algorithm. The word radix, by definition, refers to the base or the number of unique digits used to represent numbers. In radix sort, we sort the elements by processing them in multiple passes, digit by digit. 

Each pass sorts elements according to the digits in a particular place value, using a stable sorting algorithm (usually counting sort as a subroutine). It can be implemented to start the sorting from the least significant digit (LSD) or the most significant digit (MSD). 

You might’ve guessed this by now — the number of passes required to fully sort the elements is equal to the number of place values (digits) present in the largest element among all the input elements to be sorted. These passes continue to run for each place value until the sorting is done. 

Radix sort generally uses counting sort as an intermediate sorting algorithm. This article will show you how counting sort is used in radix sort, but we encourage you to brush up on the counting sort algorithm before reading on.

Applications of Radix Sort 

Here are a few applications of the radix sort algorithm:

• Radix sort can be applied to data that can be sorted lexicographically, such as words and integers. It is also used for stably sorting strings. 
• It is a good option when the algorithm runs on parallel machines, making the sorting faster. To use parallelization, we divide the input into several buckets, enabling us to sort the buckets in parallel, as they are independent of each other. 
• It is used for constructing a suffix array. (An array that contains all the possible suffixes of a string in sorted order is called a suffix array. For example: If the string is “sort,” then the suffix array SA[] will be:
  

SA[0] = “or” 
SA[1] = ”ort” 
SA[2] = ”sort” 
SA[3] = ”t”

How Does Radix Sort Work?

What better way to understand the working of a sorting algorithm than with the help of an illustrative example? Let’s jump right in!

Radix Sort Example: LSD to MSD

The following array needs sorting:

Array[] = {455, 61, 63, 45, 67, 135, 74, 49, 15, 5}

Here’s how we do this using radix sort:

• We start off by finding the maximum element in the unsorted input array (maxim). The number of digits (d) in maxim gives us the number of passes we need to run to get the fully sorted output.
• Here, the maxim = 455 and d = 3. This tells us that 3 passes will be required to fully sort the array
• The loop will run once for units place, once for the tens place, and once for hundreds place before the array is finally sorted.

• This array consists of integers in the decimal number system —  so the digits will range from 0 to 9. We have to maintain a count of 10 digits for each place value since the base (or radix) is 10. Now, we know we’ll need a count array of size 10.
• We start sorting from the least significant digit (LSD). 

Note:  “135 is before 15” and “15 is before 5” despite the same units place (5) because that’s the order in which they occur in the original array. This is a feature of stable sorting algorithms.

• Once the array is sorted based on units place, we sort the result of the previous step based on tens place. Finally, we sort the result based on hundreds place (MSD).

After the final pass, we get the sorted array. 

Radix Sort Example: MSD to LSD

In the previous example, we sorted from LSD to MSD. If we’d gone the other way, we would have got the same result. However, we prefer sorting from LSD to MSD — the benefit is that after any n passes, positions of all numbers with digits <= n are sorted relative to each other.

There are certain cases where it is more advantageous to implement radix sort from MSD to LSD. One such case is when we have to sort strings in alphabetical order. In this case:

• The radix will be 26, as there are 26 letters in the alphabet. 
• We need to go from the first letter of the string (MSD) to LSD as the string lengths may not be equal. 
• LSD to MSD will not work. Look at this example:

The right sorted order for the above example is {abc, ac, cba}, which we’ll get if we move from MSD to LSD. 

In the case of digits, the number of place values of numbers with fewer digits can effectively match that of the largest number since there can be as many zeroes to the left of any number as needed — we’re effectively comparing, say, 0034 with 2139. There’s no such equivalent for strings.

We can go LSD to MSD if the strings are of the same length. For example:

While sorting from MSD to LSD, we need to use buckets to separate the result of previous passes to get the correct result. For example, without buckets:

This error happened because the LSD got more priority than the MSD. The fix for this error is to use buckets:

Radix Sort Algorithm

Here’s the algorithm for radix sort:

Radix Sort (Array, sizeArray)

‍Step 1: Find the largest element in the unsorted input array (Array)

Step 2: Create a for expression that loops d times, where d = number of digits in the largest element (maxim)

Step 3: For the first place value, call counting sort, jump place value by 10 to move to the next significant digit

Step 4: Continue step 3 for all place values (finish all d passes)

Step 5: Print out the updated, sorted array.

Step 6: Exit

Here's what's happeing:

1. We first find the maximum element in the array (maxim) and then call radix sort on that array. 
2. Within radix sort, we call counting sort “d” times (d = number of digits in maxim). If all the place values in the maximum number are sorted, the whole array must be sorted.
3. With each loop, we are jumping to the next significant digit. 
4. Radix sort calls counting sort as long as maxim/place > 0 (“place” starts from 1 and jumps by a factor of 10 each time. This works because “maxim/place > 0” will be satisfied as many times as the number of digits in the maxim.) 

For example, if maxim = 456, 456/1>0, 456/10>0, 456/100>0, 456/1000<=0 and so the loop will stop after running thrice. 

Note: a/b generally means floor(a/b), that is, 456/1000 evaluates to 0.

Once the loop has run counting sort for all place values, we finally have our sorted output.

Radix Sort Pseudocode

Following is the pseudocode for radix sort. Use this to implement radix sort in any programming language of your choice.

radixSort()

Find largest element (maxim) in the input array array[]

For each place value in input (place=1;maxim/place>0;place*=10)

           Sort all elements on the basis of digits in that place value  

using counting sort

  For each array[] index (i=0;i<size;i++)

   Store all the sorted elements in the original array 

Output the sorted array[]

end radixSort()

Radix Sort Code

We’ve used C++ to demonstrate the implementation of radix sort:

#include <bits/stdc++.h>

using namespace std;

// Counting sort is run via the function radixSort for each place value.

void countingSort(int array[], int sizeArray, int placeValue) 

{

  // For each digit from 0 to 9

  const int base=10;

  int sortedArray[sizeArray]; 

    // Initializing all elements of the count array to 0.

int count[base]={0}; 

    // Looping through array and counting the occurrences of unique digits 

    // at the currently relevant place value.

for(int i=0; i<sizeArray; i++)

    {

      // The following variable represents the digit at the currently 

      // relevant place value. And place value jumps by 10 each time.

      // For instance, when placeValue is 1, (345/1)%10 gives 5, when it is 

      // 10, (345/10)%10 gives 4, and so on.

  int digitAtPlaceValue=(array[i]/placeValue)%10;

      // Incrementing the count of the digit we find at that place value.

  count[digitAtPlaceValue]++;

    }

      // Note that count now stores the cumulative count of the unique 

      // digits. Since indexes representing digits are in increasing order 

      // cumulative order can be used to find sorted order.

    // Storing cumulative counts in the count array, which stored 

    // the absolute counts before.

for(int i=1; i<base; i++)

    {

      count[i]+= count[i-1];

}

    // Sorting elements in increasing order of digits at the currently 

    // relevant place value. Loop is run from right to left 

    // to maintain the stability of the sort.

    for(int i = sizeArray - 1; i >= 0; i--) 

{

            int digitAtPlaceValue=(array[i]/placeValue)%10; 

      // The following expression tells us where to store the number 

      // corresponding to a digit when sorting for this pass.

      int sortedIndex=count[digitAtPlaceValue]-1;      

      // Storing the array element at its correct sorted position for this 

      // pass.

      sortedArray[sortedIndex]=array[i];

      // Updating the cumulative count of the digit after storing one.       count[(array[i]/placeValue)%10]--;   

}

    // Updating the original array with the sorted result of this pass, so 

    // that it can be the input that is sorted in the next pass, based 

    // on the next place value.

for(int i=0;i<sizeArray;i++)

      array[i]=sortedArray[i];

}

// Sorts the input array by running counting sort for each place 

// value that exists in the input (or in the max element of it.)

void radixSort(int array[], int sizeArray) 

{

  // Computing the maximum element. 

  int maxim= *max_element(array, array + sizeArray); 

  // Since place value increments by a factor of 10, maxim/placeValue >0 

  // is true only for the number of times = the number of digits in maxim.

  for(int placeValue=1; maxim/placeValue>0; placeValue*=10)

    // Running counting sort for each place value.

    countingSort(array, sizeArray, placeValue);

}

int main() 

{

int array[]={455, 61, 63, 45, 67, 135, 74, 49, 15, 5};

int sizeArray =10;

radixSort(array,sizeArray);

for(int i=0; i<sizeArray; i++)

cout<< array[i] << " ";

return 0;

}

Output

We’ll now let’s walk through how the radix sort algorithm runs to give the desired sorted array.

Input array: {455, 61, 63, 45, 67, 135, 74, 49, 15, 5} 

PASS 1: UNITS DIGIT

Count array:

Count array after storing the count of each unit digit in the original array:

Count array after storing the cumulative count so that their values indicate their sorted positions:

Next, we go through the original array from right to left (since the cumulative count will give the last element’s position first). 

The rightmost digit in the original array has 5 in the unit place. The value at index 5 of the count array is 8. 

So, 8 - 1 = 7 is both the new value at index 5 of the count array as well as the index at which we will place the rightmost number 5 in the sorted array after the first pass. 

Similarly, we find out the positions of the remaining elements in the input array, moving from right to left.

Array after pass 1:

PASS 2: TENS DIGIT

Count array:

Count array after storing the count of each tens digit in the resultant array of pass 1:

Count array after storing the cumulative count so that their values indicate their sorted positions:

In the second pass, 49 is the rightmost digit with 4 at the tens place. At index 4 of the count array, the cumulative value is 5

Therefore, 5 - 1 = 4 is both the updated value at index 5 of the count array as well as the index at which 49 will be placed in the sorted array after the second pass.

After pass 2:

Note that after pass 2, all the two-digit numbers are sorted relative to each other.

PASS 3: HUNDREDS DIGIT

Count array:

Count array after storing the count of each tens digit in the resultant array of pass 1:

Count array after storing the cumulative count so that their values indicate their sorted positions:

Like the last two passes, we start from the rightmost digit, 74, which has 0 in its hundreds place. At the index 0 of the count array, the cumulative value stored is 8. 

So 8 - 1 = 7 is the updated value of count[0] as well as the index at which 74 will be stored in the final sorted array. 

(We know only three passes are required as the maximum number 455 has only 3 digits.)

After pass 3:

The output is this final sorted array after all three passes.

Radix Sort Complexity

Since radix sort uses an intermediate stable sorting algorithm, the complexity of the intermediate algorithm affects the overall complexity of radix sort and the number of passes required to sort the array fully.

Radix Sort Time Complexity

For the radix sort implementation that uses counting sort as an intermediate stable sort, the time complexity for worst-, best- and average-case scenario is O(d*(n+b)). 

Here, 

• d is the number of digits in the maximum number
• O(n+b) is the time complexity of counting sort, where b is the base of the number system used.

The complexity of counting sort is O(n+b) because there are four for loops, three of them iterating n times, one iterating b times  — O(3n+b) or O(n+b). 

The time complexity for radix sort is O(d*(n+b)) because counting sort is called d times.

Radix Sort Space Complexity

Space complexity of radix sort is O(n+b) because we use a couple of additional arrays — count array of size b and sorting array of size n.

Strengths of Radix Sort

1. As a non-comparison-based sorting algorithm with linear time complexity, radix sort has an advantage over comparative sorting algorithms with O(n logn) as their time complexity. 
2. Radix sort is also faster when the range of the array elements is relatively narrow, but the count of elements to sort is high. It is also much quicker when the algorithm is being run concurrently on parallel machines.
3. Since the radix sort algorithm sorts digit by digit, the number of possible digits is limited to the base of the number system used. This means that it can sort multi-digit numbers (like 15 digit numbers) without increasing the range of digits over which the sorting must be done. The range remains 0 to 9 for numbers in the decimal number system, regardless of number size. This is an advantage since an increased range of digits to sort might decrease the algorithm’s efficiency.

Weaknesses of Radix Sort

1. For very large numbers or a number system with a wider base, radix sort can perform in linear time; however, the subroutine sort requires larger space for the auxiliary array it uses to sort. This increases the space requirements, making it not ideal for such cases where space is important. (For example, software libraries). 
2. Implementation of radix sort is different for different data types, and the algorithm depends on digits or letters. Hence, it is less flexible than other sorting algorithms. The implementation has to be re-evaluated and altered based on each data type.
3. Although the asymptotic time complexity of the radix sort is promising, in reality, it doesn't perform well because of the hidden large constant factor involved. For example, when the count of digits is very high, and the number of inputs in the array is very small. And it also takes more space compared to quicksort, which, unlike radix sort, also sorts in-place. 

Radix Sort FAQs

Question 1: Is radix sort a stable sorting algorithm?

Answer: Yes. Radix sort uses a stable sorting algorithm as its subroutine, preserving the relative order of two elements with the same key. Hence, radix sort is a stable sorting algorithm. (A sorting algorithm is stable if, for any two elements with the same key, the relative order of the two elements is preserved in the sorted output as it is in the original input.)

Question 2: Is radix sort an in-place sorting algorithm?

Answer: Since in radix sort, auxiliary data structures like arrays are used to sort the input array. The sorting process does not happen within the original array. Therefore, it is not an in-place sorting algorithm.

Question 3: How is radix sort different from bucket sort?

Answer: Radix sort and bucket sort are pretty similar; however, there’s one significant difference between the two. In bucket sort, sorting happens only from the most significant digit (MSD) to the least significant digit (LSD). On the other hand, in radix sort, the implementation can go from MSD to LSD or LSD to MSD — there’s no restriction.

Are You Ready to Nail Your Next Coding Interview?

If you’re looking for guidance and help with getting your prep started, sign up for our free webinar. As pioneers in the field of technical interview prep, we have trained thousands of software engineers to crack the toughest coding interviews and land jobs at their dream companies, such as Google, Facebook, Apple, Netflix, Amazon, and more!

Sign up now!

----------

Article contributed by Tanya Shrivastava