[Haskell-cafe] YOrd and ysort

[Krzysztof Skrzętnicki]

The ysort function I've written for YOrd class was incredibly
inefficient. Here is better one:

ysort :: (YOrd a) => [a] -> [a]

ysort = head . mergeAll . wrap

wrap :: [a] -> [[a]]
wrap xs = map (:[]) xs


mergeAll :: (YOrd a) => [[a]] -> [[a]]
mergeAll [] = []
mergeAll [x] = [x]
mergeAll (a:b:rest) = mergeAll ((merge a b) : (mergeAll rest))


merge :: (YOrd a) => [a] -> [a] -> [a]
merge [] [] = []
merge xs [] = xs
merge [] xs = xs
merge xs ys = let ((sm:smS),gts) = xs `ycmp` ys in
              smS `seq` gts `seq` sm : (merge smS gts)