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

Bayley, Alistair Alistair.Bayley at invesco.com
Mon Dec 29 10:43:02 EST 2008

> From: haskell-cafe-bounces at haskell.org 
> [mailto:haskell-cafe-bounces at haskell.org] On Behalf Of Adrian Neumann
> 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.

Your single module might be benefiting from optimisation; specifically,
specialisation to Ints, which would allow the dictionary lookup to be
removed. Can you get the same performance if you move your mergeSort &
qs functions into a separate module, and only export mergeSort & qs?

Confidentiality Note: The information contained in this message,
and any attachments, may contain confidential and/or privileged
material. It is intended solely for the person(s) or entity to
which it is addressed. Any review, retransmission, dissemination,
or taking of any action in reliance upon this information by
persons or entities other than the intended recipient(s) is
prohibited. If you received this in error, please contact the
sender and delete the material from any computer.

More information about the Haskell-Cafe mailing list