[Haskell-cafe] Sorting with a weaker form of Ord (Re: Type constraints for class instances)

apfelmus apfelmus at quantentunnel.de
Mon Mar 24 18:06:43 EDT 2008

apfelmus wrote:
> Krzysztof Skrzętnicki wrote:
>> class YOrd a where
>>     ycmp :: a -> a -> (a,a)
>> Unfortunately, the performance of ysort is rather low. I believe that
>> it is impossible to create any sorting algorithm that uses ycmp
>> instead of compare, that is faster than O(n^2).
> It is possible, the following implementation of  mergesort  is O(n log 
> n) :)
>     merge3 x []     xs = x  : xs
>     merge3 x (y:ys) xs = x' : merge3 y' xs ys
>         where (x',y') = x `ycmp` y
> invariant that  x  became  candidate by winning over all  xs

Oops,  merge3  clearly violates this invariant since  y'  could be  x . 
So, my previous post is all wrong  λ(>_<)λ .


More information about the Haskell-Cafe mailing list