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

Krzysztof Skrzętnicki gtener at gmail.com
Mon Dec 29 17:53:51 EST 2008

I think you are repeating my steps :-) On sorted data (like [1..n])
quicksort is O(n^2).

Please read this thread:

All best

Christopher Skrzętnicki

2008/12/29 Adrian Neumann <aneumann at inf.fu-berlin.de>:
> Ah that's interesting. Now my Mergesort is exactly as fast as List.sort. I
> thought GHC was smart enough to do that kind of inter-module optimisation.
> Still, Quicksort is twice as fast, so at least one argument for a
> Data.List.Sort package on hackage remains.
> Am 29.12.2008 um 16:43 schrieb Bayley, Alistair:
>>> 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?
>> Alistair
>> *****************************************************************
>> 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.
>> *****************************************************************
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe

More information about the Haskell-Cafe mailing list