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