I've just started learning Haskell and am trying to implement some basic algorithms. My shot at merge sort looks like this:
mergeSort :: Ord a => [a] -> [a]
mergeSort [] = []
mergeSort [x] = [x]
mergeSort xs = merge (mergeSort as) (mergeSort bs)
where
(as, bs) = splitInHalf xs
splitInHalf :: [a] -> ([a], [a])
splitInHalf [] = ([], [])
splitInHalf [x] = ([x], [])
splitInHalf (x:y:xys) = (x:xs, y:ys)
where (xs, ys) = splitInHalf xys
merge :: Ord a => [a] -> [a] -> [a]
merge xs [] = xs
merge [] ys = ys
merge (x:xs) (y:ys) = if x < y
then x:(merge xs (y:ys))
else y:(merge ys (x:xs))
As far as I can tell, my implementation is more or less the same as on rosetta code [0], literate programs [1] and several stack overflow questions [2][3].
The algorithm works, but for large lists (for example, 500k random numbers), I get a stack overflow.
So my question is: How can I change my code so that it works on larger inputs? Or, more generally, how can I write recursive algorithms in functional languages that require more nested function calls than fit in the stack?