マージソート
ボトムアップの分割統治法を用いたソートアルゴリズム.
データを分割する
各々をソートする
マージする
以下 haskell の実装(安定ソートではない)
merge :: Ord a => [a] -> [a] -> [a] merge [ ] [ ] = [ ] merge xs [ ] = xs merge [ ] ys = ys merge (x:xs) (y:ys) | x <= y = x : merge xs (y:ys) | otherwise = y : merge (x:xs) ys msort :: Ord a => [a] -> [a] msort [ ] = [ ] msort [x] = [x] msort xs = merge (msort (take center xs)) (msort (drop center xs)) where center = div (length xs) 2