8.3-5

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 case? How many piles of cards would an operator need to keep track of in the worst case?

Let recall the procedure from the book. Intuitively, you might sort numbers on their most significant digit, sort each of the resulting bins recursively, and then combine the decks in order. Unfortunately, since the cards in 9 of the 10 bins must be put aside to sort each of the bins, this procedure generates many intermediate piles of cards that you would have to keep track of.

If you see from the above the algorithm will a intermediate sort like counting sort which require $\theta(n+k)$ (we need to sort n cards since k is 10 for decimal numbers(0-9) ) and each of the buckets needs to be recursively solved. In the worst case each bucket on solving will create a new bucket with n values this will happen when we have all equal values (ex: let d =3 and n =3 123,123,123). we need to solve d buckets recursively the worst case running time is $\theta(d(n+10))$. The opertaer need to keep track of nd cards. Since each bin will have n cards if you recursively solve we get a new bin with n cards and this repeats for every digit. Since there are d digits and we have n cards the no of cards is nd.