9.9 Radix Sorting

• Here we use some special information about the keys and design sorting algorithms which beat the O(nlog n) lower bound for comparison-based sorting methods.
• Consider sorting n integers in the range 0 to n² - 1. We do it in two phases.

Phase 1:

We use n bins, one for each of the integers 0, 1, ^... , n - 1. We place each integer i on the list to be sorted into the bin numbered $$i \ \mbox{{\bf mod}} \ n$$Each bin will then contain a list of integers leaving the same remainder when divided by n.


At the end, we concatenate the bins in order to obtain a list L.

Phase 2:

The integers on the list L are redistributed into bins, but using the bin selection function:




$$\lfloor$$$${\frac{i}{n}}$$$$\rfloor$$ Now append integers to the ends of lists. Finally, concatenate the lists to get the final sorted sequence.

Example

n = 10

Initial list : 36, 9, 0, 25, 1, 49, 64, 16, 81, 4

Phase 1 : bin = i mod 10

= right most digit of i

Bin

0

0

$\bullet$

1

1

81

$\bullet$

2

3

4

64

4

$\bullet$

5

25

6

36

16

$\bullet$

7

8

9

9

49

$\bullet$

Concatenation would now yield the list:

L: 0, 1, 81, 64, 4, 25, 36, 16, 9, 49

Phase 2 : bin = $\lfloor$i/10$\rfloor$

= right most digit of i

Bin

0

0

1

4

9

1

16

2

25

3

36

4

49

5

6

64

7

8

81

9

The concatenation now yields:

0, 1, 4, 9, 25, 36, 49, 64, 81

In general, assume that the key-type consists of k components f₁, f₂, ^... , f_k, of type t₁, t₂, ^... , t_k.

Suppose it is required to sort the records in lexicographic order of their keys. That is, 

(a₁, a₂,..., a_k) < (b₁, b₂,..., b_k) if one of the following holds:

1.	a1 < b1
2.	a1 = b1;a2 < b2
3.	a1 = b1;a2 = b2;a3 < b3
	.
	.
	.
k.	a1 = b1;...;ak - 1 = bk - 1;ak < bk

Radix sort proceeds in the following way.

First binsort all records first on f_k, the least significant digit, then concatenate the bins lowest value first.

Then binsort the above concatenated list on f_{k - 1} and then concatenate the bins lowest value first.

In general, after binsorting on f_k, f_{k - 1},..., f_i, the records will appear in lexicographic order if the key consisted of only the fieldsf_i,..., f_k.
 

void radixsort;

/ * Sorts a list A of n records with keys consisting of fields

f₁,..., f_k of types t₁,..., t_k. The function uses k

arrays B₁,..., B_k of type array [t_i] of list-type, i = 1,..., k,

where list-type is a linked list of records */

{

for(i = k;i$\geq$ 1;i - -)

{

for (each value v of type t_i)

make B_i[v] empty; /* clear bins */

for (each value r on list A)

move r from A onto the end of bin B_i[v],

where v is the value of the field f_i of the key of r;

for (each value v of type t_i from lowest to highest)

concatenate B_i[v] onto the end of A

}

}
 

• Elements to be sorted are presented in the form of a linked list obviating the need for copying a record. We just move records from one list to another.
• For concatenation to be done quickly, we need pointers to the end of lists.

Complexity of Radix Sort

• Inner loop 1 takes O(s_i) time where s_i = number of different values of type t_i
• Inner loop 2 takes O(n) time
• Inner loop 3 times O(s_i) time


Thus the total time

$$\sum_{i=1}^{k}$$ =

$$\left(\vphantom{kn + \sum_{i=1}^k \space s_i }\right. \sum_{i=1}^{k} \left.\vphantom{kn + \sum_{i=1}^k \space s_i }\right)$$ =

$$\left(\vphantom{ n + \sum_{i=1}^k \space s_i}\right. \sum_{i=1}^{k} \left.\vphantom{ n + \sum_{i=1}^k \space s_i}\right) \mbox{assuming $k$\space to be a constant}$$ =

• For example, if keys are integers in the range 0 to n^k - 1, then we can view the integers as radix - n integers each k digits long. Then t_ihas range 0  ^...  n - 1 for 1 $\leq$i $\leq$k.


Thus s_i = n and total running time is O(n)

• similarly, if keys are character strings of length k, for constant k, then s_i = 128 (say) for i = 1,..., k and again we get the total running time as O(n).