mergeSort :: (Ord a) => [a] -> [a]
mergeSort xs = ms (length xs) xs
where
ms _ [] = []
ms _ [x] = [x]
ms n xs = merge (ms m as) (ms (n - m) bs)
where
m = div n 2
(as, bs) = splitAt m xs
merge xs [] = xs
merge [] ys = ys
merge xs@(x : xs') ys@(y : ys')
| x <= y = x : merge xs' ys
| otherwise = y : merge xs ys'