Radix Sort

In a previous post, I talked about Counting Sort, an O(N) sorting algorithm that is not comparison-based. If you have read the post (or you already know about Counting Sort), you may have realized that Counting Sort can be so fast simply because it deals with very simple, limited form of input - single-digit integers.

The question that naturally arise then is: can we extend Counting Sort to bigger numbers, say  a list comprising of integers of arbitrary size?

Let's try to work things out... Say we have just 2 numbers...

Can we apply Counting Sort to these numbers?? Counting Sort is only for single digit... but what if we apply it to one number position at a time, maybe start from the least significant position (the rightmost side)...

Applying Counting Sort to that 1st position (from the right, place value = 1), we get:

Then apply Counting Sort again, this time to position 2 (place value 10):

No change, of course, since it's the value 2 in that positions for both numbers. Going on to the most significant figure (the leftmost number, or place value 100), there is no change in the order, since 1 is less than 3. So the final sorted order is: 121  323.

Hmm.. things seem to look good...

Let's try with a bit more complex example:

Applying Counting Sort to the least significant position, we obtain:

Moving on the next position, there's no change in the ordering: 2 - 2 - 9. So we move on to the most significant position.

But here's a subtlety: 121 and 323 each has 3 digits, while 99 has only 2. Hence the most significant positions for 121 and 323 are not the same as that for 99. A solution to this is simple, however - simply assume a zero in from of 99, as you can see above.

Hence, applying Counting Sort to the most significant bit, we obtain:

It works, right? Well, this is Radix Sort, a sorting algorithm that applies Counting Sort to sort a sequence of integers. To do the digit by digit sorting, we can code as follows:

def radixSort(alist):
    max = max(alist)
    placevalue = 1
    while max > placevalue:
        alist = countingSort(alist,placevalue)
        placevalue *= 10
    return alist

In the code above, we first compute max, the maximum number in the input list, alist. max, being the biggest number, will of course have the maximum number of digits. We start with the least significant position, at placevalue = 1,  and multiply placevalue by 10 at every iteration. The loop ends when placevalue is more than max.

The function countingSort itself needs a slight modification from the one shown in the post on Counting Sort. We need to pass in place value as a parameter, and use it to sort numbers based on the digits at the corresponding position.

def countingSort(arr, placevalue):
    n = len(arr)

    output = [0] * n
    count = [0] * 10

    for i in range(n):
        num = (arr[i]//placevalue)
        index = num%10
        count[index] += 1

    for i in range(9):
        count[i+1] += count[i]
     
    for i in range(9, 0, -1):
        count[i] = count[i-1]
    count[0] = 0
 
 
    for i in range(len(arr)):
        num = (arr[i]//placevalue)
        index = num%10
        output[ count[index] ] = arr[i]
        count[index] += 1

    return output