[Haskell-beginners] Merge Sort Stack Overflow

[Florian Lammel]

Hi,

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?

Regards
Florian

[0] http://rosettacode.org/wiki/Sorting_algorithms/Merge_sort#Haskell
[1] http://en.literateprograms.org/Merge_sort_(Haskell)
[2]
http://stackoverflow.com/questions/7554226/haskell-merge-sort-sorting-words-and-numbers
[3] http://stackoverflow.com/questions/1215432/merge-sort-in-haskell
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20130916/530a33af/attachment.htm>