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