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

_______________________________________________
Beginners mailing list
Beginners@haskell.org
http://www.haskell.org/mailman/listinfo/beginners