プログラミング Haskell 6章 再帰関数 6.8 練習問題
-- マージソート merge :: (Ord a) => [a] -> [a] -> [a] merge [ ] ys = ys merge xs [ ] = xs merge (x : xs) (y : ys) | x <= y = x : merge xs (y : ys) | otherwise = y : merge (x : xs) ys halve :: [a] -> ([a], [a]) halve xs = splitAt (length xs `div` 2) xs msort :: (Ord a) => [a] -> [a] msort [ ] = [ ] msort [x] = [x] msort xs = merge (msort ys) (msort zs) where (ys, zs) = halve xs
merge は「x が y 以下であれば x を出力に加え再帰」「y が x より小さければ y を出力に加え再帰」と考えるとすっきりする。