mergesort. Reply

[Serge D. Mechveliani]

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