Radix sort suffix invariant ($s_p(k)=k\mathrm{mod}{R}^p$)

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.