mergesort

[Simon Marlow]

> (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=20
> 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