[Haskell-cafe] Functional counterpart of counting-sort?

Hi all, I’m sorry if this is a trivial question. Everybody knows the counting sort algorithm to sort an array of integer values, which runs in O(n) time, circumventing the O(n log n) lower bound by avoiding comparison operations. Of course, that only works for integers. However, it seems to me that it essentially relies on the availability of a O(1) indexing operation on the array, not on algebraic or logical properties of the set of the integers. Do any of you know if it is possible to sort a _list_ of integers in O(n) time in a (lazy) purely functional language? I’d say no, but given all the crazy laziness tricks out there, I can’t say for sure ;) Even if no: any theoretical considerations on why not? Greetings, Nicola