Reference no: EM131953569

Radix Sort is a sorting procedure where the n keys being sorted are never compared to each other. Each number to be sorted has the same number of digits, d, and the base of the numbers, referred to as the radix is r. The radix sort goes as follows: In each of the diterations (1..d) the numbers are placed in lists numbered 0 through r-1, according to the value of the dth least significant digit. After a pass, all lists are mergedso that all elements in list 0 are followed by all elements in list 1, followed by all elements in list 2, ... with all elements in list r-1 at the end.The process repeats for all digits from least significant (right-most) to the most significant (left-most). Recall a number is base r has digits 0 .. r-1.

a. Use the sequence of numbers below in base r = 3, and show each iteration result of the radix sort.

201 200 121 011 001 022 002 222 111 110

b. Analyze the complexity of radix short for n numbers in base r, with d digits.