mergesort

[Ketil Z. Malde]

"Simon Marlow" <simonmar@microsoft.com> 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