Ketil Z. Malde
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 mechvel@botik.ru