Haskellのれんしゅう: マージソート

msort.hs

-- Merge Sort
msort :: (Ord a) => [a] -> [a]
msort [] = []
msort [x] = [x]
msort xs = merge (msort f) (msort s) 
            where
               (f,s) = split xs

split :: (Ord a) => [a] -> ([a],[a])
split xs = splitAt center xs
             where 
               center = (length xs) `div` 2

merge :: (Ord a) => [a] -> [a] -> [a]
merge xs [] = xs
merge [] ys = ys
merge xs'@(x:xs) ys'@(y:ys)
  | x < y   = x : merge xs ys'
  | otherwise = y : merge xs' ys

-- Test
main = do
  print $ msort [4,3,1,2,7,5]
  print $ msort ["catch","fax","cat","dog","fox"]