A stable sorting algorithm is one which preserves the order of duplicate key entries when sorted. In other words, if entries e1 and e2 have the same key k, and e1 appears before e2 in the input, then e1 will appear before e2 in the sorted output.

a) Is quicksort stable? Prove your answer, detailing every step that you take to arrive at the conclusion

b) Suppose you use radix sort to sort countries according to ascending order of population. The populations are read in as text, and digits are extracted using the Character.digit(char ch, int radix) method. What is the worst case number of unit time operations that would be performed to sort this list? State the unit time operations, and show the derivation of your result. (You may want to use the fact that there are about 190 countries, and China has the largest population, of around 1.3 billion.)

c) For the sorting problem described in (b), describe the fastest (in real time, not big O) possible implemenation you can think of. (Side note: Vatican City has a population of 800). Detail the data structure and the process. You can use any of the sorting algorithms (except radix sort, which you have already analyzed in part b).