= Radix sort suffix invariant
{title2=$s_p(k)=k\bmod R^p$}
After $p$ passes, $0\le p\le d$, the <array> is in nondecreasing order of $s_p(k)=k\bmod R^p$, the <integer> represented by its $p$ lowest <numerical digits>. Equivalently it is ordered by the <tuple> $(\delta_{p-1}(k),\ldots,\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\bmod1=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. Since
$$
s_{p+1}(k)=R^p\delta_p(k)+s_p(k),\qquad 0\le s_p(k)<R^p,
$$
the 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>.
Back to article page
