Past exam of the year 1 of the computer science course of the University of Oxford / 2016 / Functional programming, design and analysis of algorithms (resit) / 6 / e / Solution

For bare characters, equal occurrences are indistinguishable. The count-and-reconstruct implementation in (d) nevertheless 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.