Comp 122

linsort - 17

Lin / Devi

Comp 122

# Correctness of Radix Sort

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.