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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
