Does counting sort require mutation?
First off, a persistent map from address to value can simulate RAM. There is a time overhead of $O(\log(s))$ and a space overhead of $O(s)$, where $s$ is the space used.* So an algorithm that runs in time $t$ and space $s$ in RAM has a purely functional algorithm in time $O(t \log(s))$ and space $O(s)$. However, simulating the RAM itself, at least conceptually, creates a purely functional computer, not version of the particular algorithm in question, so it probably isn't what you're looking for.

Fortunately this algorithm can be tweaked slightly to be purely functional. Using a persistent sorted map from list item to count, you can traverse the list, updating the count in the map for each list item encountered in $\theta(n \log(c))$ time and $\theta(c)$ space, excluding input and output lists, where $c$ is the number of distinct values. Then, you can concatMap the (list item, count) pairs to count occurrences of the list item. As the map is already sorted by list item, the resulting list will be sorted.

The original algorithm runs in $\theta(n)$ time and $\theta(c)$ mutable space, excluding input and output lists, so the functional version introduces a factor of $\log(c)$ in its run time, which is the same factor introduced by simulating the RAM.



* Specifically, as far as time is concerned, $s$ is the mutable space used, as any immutable space can be provided separately in a read-only array so it doesn't impose any time penalty.