Radix Sort

 Radix Sort

Radix sort processes the elements the same way in which the names of the students are sorted according to their alphabetical order. There are 26 radix in that case due to the fact that, there are 26 alphabets in English. In the first pass, the names are grouped according to the ascending order of the first letter of names.

In the second pass, the names are grouped according to the ascending order of the second letter. The same process continues until we find the sorted list of names. The bucket are used to store the names produced in each pass. The number of passes depends upon the length of the name with the maximum letter.

In the case of integers, radix sort sorts the numbers according to their digits. The comparisons are made among the digits of the number from LSB to MSB. The number of passes depend upon the length of the number with the most number of digits.

Complexity

Complexity	Best Case	Average Case	Worst Case
Time Complexity	Ω(n+k)	θ(nk)	O(nk)
Space Complexity			O(n+k)

Example

Consider the array of length 6 given below. Sort the array by using Radix sort.

A = {9007, 0143, 0010, 6001, 0901, 0099, 1985, 0512, 1024}

Pass 1: (Sort the list according to the digits at 0's place)

Input	0	1	2	3	4	5	6	7	8	9	Output
9007								9007			0010
0143				0143							6001
0010	0010										0901
6001		6001									0512
0901		0901									0143
0099										0099	1024
1985						1985					1985
0512			0512								9007
1024					1024						0099

Pass 2: (Sort the list according to the digits at 10's place)

Input	0	1	2	3	4	5	6	7	8	9	Output
0010		0010									6001
6001	6001										0901
0901	0901										9007
0512		0512									0010
0143					0143						0512
1024			1024								1024
1985									1985		0143
9007	9007										1985
0099										0099	0099

Pass 3: (Sort the list according to the digits at 100's place)

Input	0	1	2	3	4	5	6	7	8	9	Output
6001	6001										6001
0901										0901	9007
9007	9007										0010
0010	0010										1024
0512						0512					0099
1024	1024										0143
0143		0143									0512
1985										1985	0901
0099	0099										1985

Pass 4: (Sort the list according to the digits at 1000's place)

Input	0	1	2	3	4	5	6	7	8	9	Output
6001							6001				0010
9007										9007	0099
0010	0010										0143
1024		1024									0512
0099	0099										0901
0143	0143										1024
0512	0512										1985
0901	0901										6001
1985		1985									9007

Therefore, the list generated in the step 4 is the sorted list, arranged from radix sort.

0010, 0099, 0143, 0512, 0901, 1024, 1985, 6001, 9007.