import Data.List

merge :: Ord a => [a] -> [a] -> [a]
merge x [] = x
merge [] y = y
merge (x:xs) (y:ys) = case compare x y of
                           LT -> x : merge xs (y:ys)
                           _ -> y : merge (x:xs) ys

mergesort :: Ord a => [a] -> [a]
mergesort [x] = [x]
mergesort list = merge left right where
                   split = splitAt (length list `div` 2) list
                   left = mergesort $ fst $ split
                   right = mergesort $ snd $ split