undefined

Exercise 2 (35 points) Radix Sort RADIX-SORT(A, d) 1 for i = 1 to d 2 use a stable sort to sort array A on digit i Suppose that we are given a sequence A of n 32-bit numbers (21, 22, .., an) to sort. The objective of this exercise is to produce the most efficient strategy to use Radix Sort to sort Sequence A. a) (2 points) In order to use Radix Sort, you must express each number using digits. Which base (2, 4, 8, 10, or 16) should you use to implement Radix Sort? Justify your choice. In other words, explain why your choice is better than the others. b) (2 points) Given the base you chose, what is the range of each digit? c) (3 points) Given the base you chose, how many digits does each number a have? d) (4 points) Given the base you chose, how will you extract each digit? In other words, explain how you can extract each digit for the number expressed in the base you chose. e) (4 points) Which algorithm will you select to sort your sequence based on each digit dh? Justify ) (15 points) Describe precisely your implementation of Radix Sort (especially the stable sort) based on the answers you provided so far. g) (5 points) Analyze the running time and space complexity of your algorithm