merge :: Ord a => [a] -> [a] -> [a]

merge xs [] = xs

merge [] xs = xs

merge ax@(x:xs) ay@(y:ys) =

    | x <= y = x : merge xs ay

    | otherwise = y : merge ax ys


mergeSort :: Ord a => [a] -> [a]

mergeSort [] = []

mergeSort [x] = [x]

mergeSort xs = merge (mergeSort ys) (mergeSort zs)

    where (ys, zs) = splitAt (length xs `div` 2) xs