linsort - 17
Lin / Devi
By induction hypothesis, the sort of the low-order d – 1 digits works, so just before the sort on digit d , the elements are in order according to their low-order d – 1 digits. The sort on digit d will order the elements by their dth digit.
Consider two elements, a and b, with dth digits ad and bd:
If ad < bd , the sort will place a before b, since a < b regardless of the low-order digits.
If ad > bd , the sort will place a after b, since a > b regardless of the low-order digits.
If ad = bd , the sort will leave a and b in the same order, since the sort is stable. But that order is already correct, since the correct order of is determined by the low-order digits when their dth digits are equal.