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.^[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.