TAOCP 5.2.5 Exercise 2
Algorithm R performs a sequence of $p$ distribution passes, each pass grouping records into $M$ FIFO queues according to a single digit $a_{p+1-k}$.
Section 5.2.5: Sorting by Distribution
Exercise 2. [**] [13] Is Algorithm R a stable sorting method?
Verified: yes
Solve time: 1m25s
Algorithm R performs a sequence of $p$ distribution passes, each pass grouping records into $M$ FIFO queues according to a single digit $a_{p+1-k}$. Within a fixed pass, the only modification of links is performed by step R4, which executes
$$ \text{LINK}(\text{TOP}[i]) \leftarrow P,\quad \text{TOP}[i] \leftarrow P, $$
so each pile is extended only at its rear, and earlier elements in the same pile remain ahead of later ones. Hence, within a single pass, the relative order of all records that receive the same digit value $i$ is preserved in the order in which they are encountered during step R3–R5 traversal.
The traversal order is fixed for each pass (for $k=1$ it runs from $R_n$ down to $R_1$, and for $k>1$ it follows the linked list produced by the previous pass), so records with identical $p$-tuples are never separated by any digit test and always remain in the same relative order throughout all passes. Since each pass preserves the order within each digit class and later passes operate on the already stable ordering produced by earlier passes, no inversion of equal keys can occur.
Therefore, Algorithm R is a stable sorting method. ∎