Radix Sort Algorithm — A Comprehensive Analysis
Explained With an Example and a Thorough Analysis of the Algorithm
Sorting is an important task in data. There are a lot of sorting techniques and based on the scenarios, we are using them. In this article, we’re going to see about a famous and interesting sorting algorithm.
What will happen if the array is to be sorted is
{10, 50, 100000, 500, 30, 900, 5}Will you still prefer to use Counting Sort? Definitely now right? Yeah, we can use but will it be the efficient approach? No! Why?
In this array, the elements are in the range of [5,100000]. That is, [1,n²]. This can result in the algorithm going O(n²) which is worse than the worse case of Counting Sorting. We are preferring linear sorting to perform faster than O(nlogn). But here, Counting Sort can go to O(n²).
So what shall be done?
In these types of situations, we can use Radix Sort!
Radix Sort
Radix sort is an integer sorting algorithm that sorts data with integer keys by clustering the keys together based on the individual digits that have the same significant position and value (place value). To sort an array of numbers, Radix sort employs counting sort as a subroutine. Radix sort works on data types other than integers because integers can be used to represent strings (by hashing the strings to integers).
The least relevant digit is sorted first, followed by the most significant digit.
The number of runs required by the Radix sort algorithm is equal to the number of digits present in the largest number in the set of numbers. For example, if the largest number is a four-digit number, the list is sorted four times.
Algorithm
radixSort(array)
d <- maximum number of digits in the largest element.
create d buckets of size 0-9.
for i <- 0 to d
sort the elements according to i th place digits using
countingSort.countingSort(array, d)
max <- find largest element among dth place elements.
initialize count array with all zeros.
for j <- 0 to size
find the total count of each unique digit in dth place of
elements and store the count at jth index in count array.
for i <- 1 to max
find the cumulative sum and store it in count array itself.
for j <- size down to 1
restore the elements to array.
decrease count of each element restored by 1.Let’s see how it works by using a simple example.
A: [150, 56, 85, 60, 1202, 924, 12, 45]
Sorting by the least significant digit (1s place) yields.
B: [150, 60, 1202, 12, 924, 85, 45, 56]
Here, we keep 1202 before 12 because it appeared before 12 in the original (A) list, and we do the same for pairs 150 and 60 and 85 and 45.
Sorting by the next digit (10s place) yields.
C: [1202, 12, 924, 45, 150, 56, 60, 85]
Here, we keep 150 before 56 because it appeared before 56 in the 2nd/ previous (B) list.
Sorting by the next digit (100s place) yields.
D: [12, 45, 56, 60, 85, 150, 1202, 924]
Sorting by the next digit (1000s place) yields.
E: [12, 45, 56, 60, 85, 150, 924, 1202]
It is done. We have sorted the given array. As we had 4 digits at maximum, we sorted the digits starting from 1s 10s 100s, and 1000s.
Check the following sorting as well.
Implement the Radix Sort Algorithm in Java
What will be the output?
[12, 45, 56, 60, 85, 150, 924, 1202]Time and Space Complexities
Radix sort has advantages over comparative sorting algorithms because it is a non-comparative algorithm. Radix sort will perform on n d-digit numbers where each digit can have up to b different values (since b is the base being used). In base 10, for example, a digit can be 0, 1, 2, 3, 4, 5, 6, 7, 8, or 9.
On each digit, the radix sort employs a counting sort. Each pass over n d-digit numbers will take O(n+b) time, with a total of d passes. As a result, the total run time of radix sort is O(d(n+b)). When d is constant and b is not much larger than n (b=O(n)), the radix sort takes linear time.
Worst Case: O(n)
Best Case: O(n)
Average Case: O(n)
If we use very large digit numbers or a large number of other bases, such as 32-bit and 64-bit numbers, it can implement in linear time, but the intermediate sort takes up a lot of space. As a result, radix sort space is inefficient. This is why this type is not used in software libraries.
Radix Sort Applications
Radix sort is implemented in
- DC3 algorithm (Kärkkäinen-Sanders-Burkhardt) while making a suffix array.
- places where there are numbers in large ranges.
Stability of Radix Sort
Radix Sort is an integer sorting algorithm that is dependent on a stable sorting subroutine. It is a sorting algorithm that does not use comparisons to sort a collection of integers. It categorizes keys based on individual digits with the same significant position and value.
Let’s unpack the formal definition and restate the basic idea:
for each digit 'k' from the least significant digit (LSD) to the most significant digit (MSD) of a number:
apply counting-sort algorithm on digit 'k' to sort the input arrayRadix Sort includes Counting Sort as a subroutine. Counting Sort is a stable integer sorting algorithm. We don’t need to know how it works, but the Counting Sort is stable.
The order from previous invocations is preserved with each invocation of the Counting Sort subroutine. For example, when sorting by the tens’ place digit (second invocation), 9881 shifts downwards but remains above 9888, preserving their relative order.
Thus, Radix Sort makes use of the Counting Sort algorithm’s stability to provide linear time integer sorting.
There is another way to prove it. Just think about how this algorithm works for two numbers (say 25 and 21). Sort them! Just try!
Parallelizability of Radix Sort
Radix Sort can be Parallelized. How? Have some work on it and share your thoughts.
Hope it helps. Share your thoughts too.
