[Haskell-cafe] Sorting with a weaker form of Ord (Re: Type
constraints for class instances)
apfelmus at quantentunnel.de
Mon Mar 24 18:06:43 EDT 2008
> 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