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 <[email protected]>: > 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: [email protected] >>> [mailto:[email protected]] 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 > [email protected] > http://www.haskell.org/mailman/listinfo/haskell-cafe > >
_______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
