"Simon Marlow" <[EMAIL PROTECTED]> writes: > 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 _______________________________________________ Glasgow-haskell-users mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
