[Algo] Exercise 8.3

Exercise 8.3-2
Which of the following sorting algorithm are stable: insertion sort, merge sort, heapsort, and quicksort? Give a simple scheme that makes any sorting algorithm stable. How much additional time and space does your scheme entail?
solution:
(1) insertion sort, merge sort are stable.
(2) We store the index value of each element, and compare the index value if there is a tie. Thus, the additional time requirement will not be affected asymptotically due to adding constant work only during comparison. The additional space requirement is that we require $\lg n$ bits to store index value resulting in $O(n\lg n)$ bits additional space.

Exercise 8.3-3
Use induction to prove that radix sort works. Where does your proof need the assumption that the intermediate sort is stable?
solution:
Basis: If $d = 1$, sorting on that digit sorts the array correctly.
Inductive step: Assume that RADIX-SORT sorts $d-1$ digits correctly. Consider two elements $a$ and $b$, with their $d$th digit $a_d$ and $b_d$ respectively.
(1) $a_d > b_d$ and $b_d > a_d$ : RADIX-SORT works correctly, because of most significant bit dominates regardless of the lower $d-1$ digits.
(2) $a_d = b_d$ : RADIX-SORT leaves $a$ and $b$ in the same order because it is stable sort. The order is correct since lower $d-1$ digits sorts correctly. That's why we need that the intermediate sort must be stable.

Exercise 8.3-4
Show how to sort n integers in the range 0 to $n^2 - 1$ in $O(n)$ time.
solution:
Using Lemma 8.4, we know that $k = n^2$, $b = \lceil 2\lg n\rceil$ and we choose $r = \lfloor \lg n\rfloor$, then RADIX-SORT can sort these numbers in $O((2\lg n / \lg n)(n + 2^{\lg n})) = O(2(n + n)) = O(n)$ running time.

Exercise 8.3-5
In the first card-sorting algorithm in this section, exactly how many sorting passes are needed to sort d-digit decimal numbers in the worst cas? How many piles of cards would an operator need to keep track of in the worst case?
solution:
There are $$1 + 10 + 10^2 + \cdots +10^{d-1} = \frac{10^d - 1}{10 - 1} = \frac{10^d - 1}{9}$$ passes needed to sort all numbers.
Each time we recursively sort numbers in a bin, we must keep track of other 9 bins. And we have to recursively sort the numbers for each digit. Hence we have to keep track of $9d$ piles of cards in the worst case.