It’s a linear time sorting algorithm which is different from the comparison based sorting algorithms like quick sort or heap sort. Counting sort is also a linear time sorting algorithm which is explained in my previous post.
Let us understand this algorithm using an example.
Consider the array [235, 10, 784, 69, 51]
We first sort the numbers based on the least significant digit, i.e the digit at 1’s place. It becomes [10, 51, 784, 235, 69]. Observe that the these numbers are now sorted according to it’s last digit ([0,1,4,5,9]).
Next we consider the digits at 10’s place and sort them. It transforms to
[10, 235, 51, 69, 784]. These are sorted according to the last but one digits ([1,3,5,6,8])
Similarly in the next step it becomes [10, 51, 69, 235, 784].
Now the entire array is sorted! We no longer need to sort array because we have at most 3 digits in any number.
Implementation details:
Suppose there are at most D digits in any number, we call the counting sort D times for each place.
Let us briefly know how counting sort works. For more details, you can check my previous post.
It first groups the numbers into buckets. The result of this is a count array of size 10 (assuming the numbers are in the range 0-9).
Calculate the prefix array of this, we get the sorted positions of given numbers.
Then we use a temporary array to arrange the numbers in sorted order.
An alternative implementation could be to maintain a list of numbers for each bucket, and merging them to a sorted array. But this approach takes extra memory for the list of buckets.
The following code shows the implementation of the above algorithm.
Exercise: Try to solve this SPOJ problem using radix sort.