Use induction to prove that radix sort works. Where does your proof need the assumption that the intermediate sort is stable?
We prove by induction that after sorting on the rightmost \(i\) digits, the array is sorted with respect to those \(i\) digits.
Base Case
After sorting on the least significant digit (position 1), all elements are correctly ordered by that digit. Elements with digit 0 come before those with digit 1, which come before those with digit 2, and so on. This is true by the correctness of the sorting algorithm used (e.g., counting sort).
Inductive Step
Inductive Hypothesis: Assume that after sorting on the rightmost \(i\) digits, the array is correctly sorted with respect to those \(i\) digits.
Goal: Show that after sorting on digit \(i + 1\), the array is correctly sorted with respect to the rightmost \(i + 1\) digits.
Consider any two elements \(x\) and \(y\) in the array after sorting on digit \(i + 1\). Let \(d_{i+1}(x)\) denote the digit at position \(i + 1\) of \(x\), and similarly for \(y\). Let \(\text{suffix}_i(x)\) denote the rightmost \(i\) digits of \(x\).
Case 1: \(d_{i+1}(x) < d_{i+1}(y)\)
The sort on digit \(i + 1\) ensures \(x\) comes before \(y\) in the output, which is correct.
Case 2: \(d_{i+1}(x) > d_{i+1}(y)\)
The sort on digit \(i + 1\) ensures \(x\) comes after \(y\) in the output, which is correct.
Case 3: \(d_{i+1}(x) = d_{i+1}(y)\)
This is where stability is essential! Since the digits at position \(i + 1\) are equal, the relative order of \(x\) and \(y\) should be determined by their rightmost \(i\) digits.
By the inductive hypothesis, before sorting on digit \(i + 1\), the array was correctly sorted by the rightmost \(i\) digits. Therefore, if \(\text{suffix}_i(x) \leq \text{suffix}_i(y)\), then \(x\) appeared before \(y\) in the array.
Because the sort on digit \(i + 1\) is stable, when \(d_{i+1}(x) = d_{i+1}(y)\), the algorithm preserves the relative order from the previous step. So \(x\) still comes before \(y\) after sorting on digit \(i + 1\), which is correct.
Conclusion
After \(d\) passes (sorting on all \(d\) digits), the array is correctly sorted. The proof requires stability to ensure that when digits at position \(i + 1\) are equal, the correct order (determined by less significant digits) is preserved.