= Least-significant-digit radix sort
A least-significant-digit radix sort processes <numerical digits> from smallest to largest <place value>. Fix <integers> $R\ge2$ and $d\ge1$, 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,\ldots,d-1$, apply a <stable digit sort> to the current <array> using
$$
\delta_j(k)=\left\lfloor\frac{k}{R^j}\right\rfloor\bmod R.
$$
The <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:
$$
(314_A,027_B,305_C,042_D,217_E,005_F,127_G,040_H).
$$
Here $R=10$, $d=3$, and leading zeros only align <place values>; $005$ represents the <integer> five. The exact pass ledger is:
$$
\begin{array}{c|llllllll}
\text{input}&314_A&027_B&305_C&042_D&217_E&005_F&127_G&040_H\\
\text{units}&040_H&042_D&314_A&305_C&005_F&027_B&217_E&127_G\\
\text{tens}&305_C&005_F&314_A&217_E&027_B&127_G&040_H&042_D\\
\text{hundreds}&005_F&027_B&040_H&042_D&127_G&217_E&305_C&314_A
\end{array}
$$
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.
\Image[/radix-sort-stable-digit-pass-ledger.png]
{title=Three stable digit passes order successively longer suffixes}
{description=Original decimal <radix sort> ledger. Each card carries an unchanged record label. Orange marks the <numerical digit> read in the current pass; green marks lower positions already processed. The suffix row beneath each pass shows precisely what is ordered, rather than claiming whole-key <sortedness> early.}
Back to article page
