(hopefully this is fairly bug-free) At least for my data (lots of values, limited range), it appears to speed things up tremendously. I haven't measured more general cases in any detail, though. And one obvious drawback may be that it's not stable, which I think can be alleviated by a few well placed 'reverse's.

I imagine you could write a pretty good bin/bucket sort using accumArray, which should be linear time in GHC. Have you tried that? Cheers, Simon