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

[Krzysztof Skrzętnicki]

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

Please read this thread:
http://www.nabble.com/(flawed-)-benchmark-:-sort-td15817832.html

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
>
>