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-... [3] http://stackoverflow.com/questions/1215432/merge-sort-in-haskell