= Stable digit sort
A <stable digit sort> applies <stable sorting> to complete <sorting records> using one specified <numerical digit> of their encoded <sort keys>. <Counting sort> can supply it; <stable record placement in counting sort> moves records without discarding their associated data. Stability concerns equal current <numerical digits>, even when the full <sort keys> differ. This is the information-preservation step in <least-significant-digit radix sort>.<Open Data Structures: An Introduction by Pat Morin/11.2 Counting Sort and Radix Sort>[Open Data Structures: An Introduction by Pat Morin; §11.2.1, associated-data and stability paragraphs; §11.2.2, least-significant passes and correctness paragraph after Figure 11.8]{ref}
An original two-record counterexample exposes the need for the tie rule. Start with $(42_A,41_B)$ at width three. A units pass gives $(041_B,042_A)$. Both tens <numerical digits> are four. A deliberately unstable tens pass may reverse their tie and return $(042_A,041_B)$: it is sorted by the tens <numerical digit>, yet its two-position suffixes $42,41$ are decreasing. The final stable hundreds pass sees two zeros and keeps this wrong order. <Sorting permutation preservation> still holds, but <sortedness> fails. Stability in the tens pass would have retained the units information.
With <counting sort> as the <stable digit sort>, each pass initializes $R$ counters, counts $n$ current <numerical digits>, constructs their <prefix sums>, and places $n$ complete <sorting records>. Thus each pass costs $O(n+R)$, and $d$ passes cost $O(d(n+R))$ in <Big O notation>. Reuse the counters and two <arrays> of record references between passes: auxiliary <space complexity> is $O(n+R)$, rather than $O(d(n+R))$. Assume constant-cost <numerical digit> extraction, counter <arithmetic>, <array> indexing and record-reference movement; the bound counts these operations, not the cost of copying arbitrarily large payloads or performing arbitrary-precision <integer arithmetic>.
The benefit is avoiding a counter for every possible whole <sort key>: width $d$ has $R^d$ possibilities, while each pass needs only $R$ counters. A larger <radix> reduces the number of passes for a fixed key range but enlarges the counter <array>. The <comparison sorting lower bound> does not apply to these direct <array indices>; they reveal more than a two-way comparison. Nor does fixing $R$ make $d$ disappear: growing key width still increases work.
Back to article page
