これまた「プログラミングHaskell」の演習問題から。比較のためにクイックソートも記載した。
merge :: Ord a => [a] -> [a] -> [a] merge xs [] = xs merge [] ys = ys 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 qsort :: Ord a => [a] -> [a] qsort [] = [] qsort (x : xs) = qsort smaller ++ [x] ++ larger where smaller = [a | a <- xs, a <= x] larger = [b | b <- xs, b > x]
実行例は以下の通り。
$ ghci 6-5.hs GHCi, version 7.6.3: http://www.haskell.org/ghc/ :? for help Loading package ghc-prim ... linking ... done. Loading package integer-gmp ... linking ... done. Loading package base ... linking ... done. [1 of 1] Compiling Main ( 6-5.hs, interpreted ) Ok, modules loaded: Main. *Main> msort [3,1,4,5,2] [1,2,3,4,5] *Main> qsort [3,1,4,5,2] [1,2,3,4,5] *Main>
