Data.List.sort, not so good?

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


_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@...
http://www.haskell.org/mailman/listinfo/haskell-cafe