マージソート

ボトムアップの分割統治法を用いたソートアルゴリズム．

1. データを分割する

2. 各々をソートする

3. マージする

以下 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