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

[apfelmus]

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  λ(>_<)λ .


Regards,
apfelmus