[Haskell-cafe] Data.List.sort, not so good?

[Adrian Neumann]

Hello Haskell-Cafe,

lately I've been playing around with sorting. I discovered that  
Data.List.sort is not as optimized I thought. At least not for random  
lists. I think we should consider adding a Data.List.Sort package to  
hackage (Similar to Data.List.Split) that offers a wide variety of  
sorting algorithms.

I don't consider myself to be a very advanced Haskell programmer, but  
I could come up with a Mergesort that beats List.sort, time- and  
spacewise.

 > http://hpaste.org/13403

On my machine List.sort takes ~10 sec, mergeSort 7, qs 4 (compiled  
with -O2). List.sort eats too much ram to sort 20.000.000 ints, my  
algorithms don't.
QuickCheck says my implementations are correct.

I suppose List.sort does clever things for nonrandom lists, that I  
didn't consider? I had a look at the source, but I couldn't find  
anything obvious.


Adrian
-------------- next part --------------
A non-text attachment was scrubbed...
Name: PGP.sig
Type: application/pgp-signature
Size: 194 bytes
Desc: Signierter Teil der Nachricht
Url : http://www.haskell.org/pipermail/haskell-cafe/attachments/20081229/7d823d3a/PGP.bin