# [Haskell-cafe] Re: Type constraints for class instances

apfelmus apfelmus at quantentunnel.de
Mon Mar 24 16:59:20 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) :)

ysort :: (YOrd a) => [a] -> [a]
ysort = head . mergeAll . map (:[])
where
mergeAll (x:y:zs) = mergeAll \$ merge x y : mergeAll zs
mergeAll xs = xs

merge []     ys = ys
merge (x:xs) ys = merge3 x ys xs

merge3 x []     xs = x  : xs
merge3 x (y:ys) xs = x' : merge3 y' xs ys
where (x',y') = x `ycmp` y

Mergesort works like a tournament and the idea is to introduce

merge3 :: YOrd a => a -> [a] -> [a] -> [a]

to make the intermediate candidates explicit. In a call

merge3 x ys zs

, the candidate  x  is pitted against the  head  of  ys . The winner is
moved to the front and the loser is the new candidate ( ycmp  is enough
to do that). Furthermore, there is the invariant that  x  became
candidate by winning over all  xs  (formally:  x <= minimum xs), there
is no need to pit  x  against them for a second time.

The whole thing is O(n log n) for the usual reasons, the important part
being that  merge3  is  O(1 + length xs + length ys). The problem with
your solution was that  merge [gt] (merge xs ys)  could be  O(2 * length
ys) or something. Both solutions are almost the same because

merge3 x ys xs  ~  merge [x] (merge xs ys)

, but  merge3  incorporates the additional insight that we don't need to
pit  x  against the  xs  anymore.

Regards,
apfelmus

```