8.3-3

8.3-3 Use induction to prove that radix sort works. Where does your proof need the assumption that the intermediate sort is stable?

Let us assume the sorting works for 1 to d-1 digits if it works for d-1 digits it works for d digits. let $a_d$ and $b_d$ be two digits to be sorted.

If $a_d > b_d$ then the algorithm places $a_d$ ahead of $b_d$ regardless of its lower order digits.

If $a_d < b_d$ then the algorithm places a_d after $b_d$ regardless of its lower order digits.

If $a_d = b_d$ then the algorithm leaves the elements in the same order they were in because it is stable. If d digits are equal the two numbers already sorted for d-1 digits and now for d- digit. If the all the digits are equal for two numbers if the intermediate sort is not stable then for the third case it will not leave the elements in the order same as the input.