Merge sort

mergesort.hs

import Data.Function

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

sort :: Ord a => [a] -> [a]
sort a = let
    half = length a `div` 2
  in
    if half == 0 then a
    else uncurry (on merge sort) $ splitAt half a