Haskellでマージソート

GHCの普通のsortはマージソートなので改めて実装する必要はないのですが、お勉強のため…
C言語などの配列に重きを置いている言語のマージソートをそのまま実装すると次のようになります。これは「配列を2分してそれぞれをマージ」という処理を再帰的に配列の要素数が0か1になるまで繰り返すというアルゴリズムです。トップダウン的な発想のアルゴリズムです。

module Main (main) where

mergesort :: [Int] -> [Int]
mergesort [] = []
mergesort [x] = [x]
mergesort xs = 
  let (xs1, xs2) = splitAt (length xs `div` 2) xs
  in merge (mergesort xs1) (mergesort xs2)
  where
    merge :: [Int] -> [Int] -> [Int]
    merge xs [] = xs
    merge [] ys = ys
    merge (x : xs) (y : ys)
      | x > y     = y : merge (x : xs) ys
      | otherwise = x : merge xs (y : ys)

main :: IO ()
main = do
  print $ mergesort [12, 14, 13, 11, 10, 16, 15]
  -- => [10,11,12,13,14,15,16]

Haskellなどリストに重きを置いている言語では、lengthとかsplitAtはコストが高いのであまり気軽には使えません(まぁ上の実装はシンプルなのでそれはそれでよいような気もしますが)。で、GHCではどうしているかというと… この続きはそのうち。