MergeSort.hs

module MergeSort(sort) where

sort :: (Ord a) => [a] -> [a]
sort [] = []
sort [a] = [a]
sort as = merge (sort firstHalf) (sort secondHalf)
  where
    (firstHalf, secondHalf) = splitAt half as
    half = (pred . length) as

merge :: (Ord a) => [a] -> [a] -> [a]
merge as [] = as
merge [] bs = bs
merge (a:as) (b:bs) = if (a < b)
  then a : merge as (b:bs)
  else b : merge (a:as) bs