merge xs [] = xs
merge [] ys = ys
merge (x:xs) (y:ys)
| x < y = x : merge xs (y:ys)
| otherwise = y : merge (x:xs) ys
mergeSort [] = []
mergeSort [x] = [x]
mergeSort xs = merge (mergeSort (left)) (mergeSort (right))
where left = take half xs
right = drop half xs
half = length xs `div` 2
main :: IO ()
main = do
print $ mergesort [1, 8, 7, 6, 2, 5, 9, 4, 0, 3]