merge xs [] = xs
merge [] ys = ys
merge (x:xs) (y:ys) = if x <= y
then x : (merge xs (y:ys))
else y : (merge (x:xs) ys)

mergesort [] = []
mergesort [x] = [x]
mergesort list = merge first_half second_half
where
(first, second) = splitAt (length list `div` 2) list
first_half = mergesort first
second_half = mergesort second