#3 Sorting larger numbers (10 pts) Suppose we have n integers in the range 0 to n4-1, and we want to sort them in O(n) time. (Since the font is small: that is n^4 - 1.)

a. (2 pts) Show that Counting-Sort is not an option by analyzing the runtime of Counting-Sort on this data. Hint: Identify the value of k and invoke the analysis that was presented in the textbook or lecture notes.

b. (3 pts) Show that unmodified Radix-Sort is not an option by analyzing the runtime of Counting-Sort on this data. Hint: Identify the value of k for each call to Counting-Sort. This is not the same as in the previous problem. Then identify the value of d, and invoke the analysis that was presented in the textbook or lecture notes.

c. (5 pts) CLRS states that we have some flexibility in how to break each key into digits, and prove a relevant Lemma 8.4. Using this as a hint, describe a modified Radix-Sort that would sort this data in O(n) time and use Lemma 8.4 to show that this is the correct runtime.