| 5.02 uses quicksort, but 5.04 will use mergesort | instead which has much more predictable performance | behaviour.
What implementation of mergesort are you using? (Could you send me code?)
It's Ian Lynagh's implementation, from a thread on this list recently: http://www.haskell.org/pipermail/glasgow-haskell-users/2002-May/003376.h tml There was some concern about the lack of laziness and stack overflows, but the general concensus was that merge sort was a better choice. Feel free to argue otherwise :) In the new libraries, I don't have any objection to providing both Data.List.mergesort and Data.List.quicksort, and even Data.List.insertionsort for almost-sorted lists. Cheers, Simon
"Simon Marlow"
There was some concern about the lack of laziness and stack overflows [of merge- vs. quicksort], but the general concensus was that merge sort was a better choice. Feel free to argue otherwise :)
I'll hereby argue for using a quicksort implementation akin to
sortBy' _ [] = [] sortBy' pc (x:xs) = let (l,e,g) = part3 (`pc` x) xs in sortBy' pc l ++ (x:e) ++ sortBy' pc g where part3 comp xs = p3 [] [] [] comp xs p3 ls es gs _ [] = (ls,es,gs) p3 ls es gs comp (x:xs) = case comp x of LT -> p3 (x:ls) es gs comp xs EQ -> p3 ls (x:es) gs comp xs GT -> p3 ls es (x:gs) comp xs
(hopefully this is fairly bug-free) At least for my data (lots of values, limited range), it appears to speed things up tremendously. I haven't measured more general cases in any detail, though. And one obvious drawback may be that it's not stable, which I think can be alleviated by a few well placed 'reverse's. Comments welcome! -kzm -- If I haven't seen further, it is by standing in the footprints of giants
participants (2)
-
ketil＠ii.uib.no -
Simon Marlow