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?
This exercise refers to the most-significant-digit-first (MSD-first) approach mentioned in Section 8.3, which sorts recursively from left to right.
Think of this as a recursive process. We first sort all cards by their most significant digit, creating 10 piles (for digits 0-9). Then we recursively sort each pile by the remaining digits. The challenge is that we need to keep track of many piles simultaneously.
A.
In the worst case, we need \(d\) passes.
Consider the recursion depth. At each level, we sort on one digit position:
- Level 1: Sort on digit 1 (most significant)
- Level 2: Sort on digit 2 within each pile from level 1
- …
- Level \(d\): Sort on digit \(d\) (least significant)
The worst case occurs when all numbers differ at every digit level, requiring us to recurse all the way down to the least significant digit. Thus, we need exactly \(d\) sorting passes.
B.
The number of piles grows exponentially with the recursion depth. At level \(i\) of the recursion (where level 1 is the root), we potentially create \(10^i\) piles.
Here’s why:
- After sorting on digit 1: Up to 10 piles (one for each digit 0-9)
- After sorting on digit 2: Each of those 10 piles splits into up to 10 sub-piles, giving \(10 \times 10 = 100\) piles
- After sorting on digit 3: Up to \(10^3 = 1000\) piles
- After sorting on digit \(d\): Up to \(10^d\) piles
In the worst case, where all possible digit combinations appear in the input, an operator must keep track of \(10^d\) piles.
This is why the section describes this approach as impractical: “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.”