= Solution
For bare characters, equal occurrences are indistinguishable. The count-and-reconstruct implementation in (d) nevertheless \b[does not preserve the identities of equal-key records], and so cannot provide <stable sorting> of associated payloads.
A stable refinement computes cumulative counts $C[j]$, the number of input keys at most $j$, then scans the original records right to left. For a record with key $j$, decrement $C[j]$ and place the complete record at output index $C[j]$. Equal-key records are placed from the end of their allocated range in reverse scanning order, preserving their original relative order. This costs $O(n+26)$ time and $O(n+26)$ auxiliary storage.
Back to article page
