merge :: Ord a => [a] -> [a] -> [a]
merge [] []         = []
merge x []          = x
merge (x:xs) (y:ys) = if x < y then x:merge (y:ys) xs else y:merge (x:xs) ys

halve :: [a] -> ([a], [a])
halve xs = (take (quot (length xs) 2) xs, drop (quot (length xs) 2) xs)

msort :: Ord a => [a] -> [a]
msort []  = []
msort [x] = [x]
msort xs  = merge (msort (fst (halve xs))) (msort (snd (halve xs)))