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

[Nicola Gigante]

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