[Haskell-cafe] YOrd and ysort

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)