24 Mar
2008
24 Mar
'08
6:06 p.m.
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