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!

1
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).

2
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 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.
3
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()

4
C Code

// C++ code for Radix Sort

#include<bits/stdc++.h>
using namespace std;

// Counting Sort function

void countingSort(int *a,int n,int div){
// Making a count array of size 10, for counting
// the frequency of digits of array elements.
int count[10];
;
// Initializing all of its
// entries with 0.
for(int i=0;i<10;i++)
count[i]=0;

// Increasing count of kth

// digit of a[i].
for(int i=0;i<n;i++)
count[(a[i]/div)%10]++;

// Updating count[i] such that count[i] now contains

// actual position of this digit in temp[].
for(int i=1;i<10;i++)
count[i]+=count[i-1];

// Making a temporary array for

// storing the output.
int temp[n];

// Building the temporary array.

for(int i=n-1;i>-1;i--){
temp[count[(a[i]/div)%10]-1]=a[i];
count[(a[i]/div)%10]--;
}

// Updating the elements in array.

for(int i=0;i<n;i++)
a[i]=temp[i];
}

// Radix Sort function

void radixSort(int a[], int n){
// Finding the maximum element
// of the array.
int max=0;
for(int i=0;i<n;i++)
if(a[i]>max)
max=a[i];

5
 // For each digit in max, calling
// the countingSort for ith digit.
for(int div=1;max/div>0;div*=10){
countingSort(a,n,div);
}
}

// Main function
int main(){
// Initializing the array.
int a[]={4,2,12,6,1,9,21};
int n=7;
// Applying the Radix sort function.
radixSort(a,n);

// Printing the array.

for(int i=0;i<n;i++)
cout<<a[i]<<" ";

return 0;
}

6
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.

7
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.

8
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.)

9
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.

10
 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.

11