Least-significant-digit radix sort

A least-significant-digit radix sort processes numerical digits from smallest to largest place value. Fix integers $R\ge 2$ and $d\ge 1$, and take $n$ complete sorting records whose sort keys satisfy $0\le k<R^d$. Use exactly $d$ positions in positional notation with radix $R$, including leading zeros. At pass $j=0,\dots ,d-1$, apply a stable digit sort to the current array usingThe floor function selects the integer quotient, and the remainder selects the current numerical digit. Move the complete sorting record, including its associated data. There are exactly $d$ passes, so this procedure terminates even for an empty array. The radix sort suffix invariant supplies its algorithm correctness argument.

For an original input, let the letters identify the attached data:Here $R=10$, $d=3$, and leading zeros only align place values; $005$ represents the integer five. The exact pass ledger is:After the units pass, the numerical digits are $0,2,4,5,5,7,7,7$. The ties retain $C$ before $F$ and $B$ before $E$ before $G$. This array is not yet ordered by its whole integer sort keys: $314$ still precedes $305$. After the tens pass, the two-position suffixes are $05,05,14,17,27,27,40,42$. In particular, $217_E$ now precedes $027_B$: their tens numerical digits differ, so stable sorting does not require retaining their previous order. The hundreds pass produces the final sorted array, with all attached letters preserved.

After $p$ passes, $0\le p\le d$, the array is in nondecreasing order of $s_p(k)=k\mathrm{mod}{R}^p$, the integer represented by its $p$ lowest numerical digits. Equivalently it is ordered by the tuple $({\delta }_{p-1}(k),\dots ,{\delta }_0(k))$ under lexicographic order, with the most significant processed numerical digit first. Among equal suffixes it retains the original order of the complete sorting records.

The loop invariant has a simple mathematical induction proof. Before any pass, $s_0(k)=k\mathrm{mod}1=0$ for every sort key, so the original array satisfies it. Suppose it holds after $p$ passes. The next stable digit sort puts smaller ${\delta }_p$ groups first and preserves the existing $s_p$ order within each tie. Sincethe new array is ordered by $s_{p+1}$. Equal new suffixes have equal current numerical digits and equal old suffixes, so their original order is also preserved. Every pass is a permutation of complete sorting records, establishing sorting permutation preservation. At termination $p=d$, the assumption $k<R^d$ gives $s_d(k)=k$: the invariant becomes whole-key sortedness, together with stable sorting.