Ketil Z. Malde <[EMAIL PROTECTED]> writes > 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!
But sortBy' (compare) [1 .. n] costs too much, even for n = 11000. It costs (on worst data) many times more than mergeSort. ----------------- Serge Mechveliani [EMAIL PROTECTED] _______________________________________________ Glasgow-haskell-users mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/glasgow-haskell-users
