[Haskell-beginners] Merge Sort Stack Overflow

[Bob Ippolito]

I an iterative solution works much better. Here's an example, using your
merge function.

mergeSort1 :: Ord a => [a] -> [a]
mergeSort1 = go . map (:[])
  where go [] = []
        go [xs] = xs
        go xss = go (mergePairs xss)
        mergePairs (xs:ys:pairs) = merge xs ys : mergePairs pairs
        mergePairs pairs = pairs

h> :!ghc -O2 Merge -fforce-recomp
[1 of 1] Compiling Merge            ( Merge.hs, Merge.o )
h> :m + Data.List
h> :load Merge
Ok, modules loaded: Merge.
h> :set +s
h> length $ let n = 1000000 in mergeSort [n, n-1 .. 1]
1000000
(5.15 secs, 2924212128 bytes)
h> length $ let n = 1000000 in mergeSort1 [n, n-1 .. 1]
1000000
(1.58 secs, 1027356744 bytes)
h> length $ let n = 1000000 in sort [n, n-1 .. 1]
1000000
(0.24 secs, 107481296 bytes)

The source to Data.List's sort is clever, you should give it a read:
http://www.haskell.org/ghc/docs/latest/html/libraries/base/src/Data-List.html#sort


On Mon, Sep 16, 2013 at 10:35 AM, Florian Lammel <mail at florianlammel.com>wrote:

> 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 at haskell.org
> http://www.haskell.org/mailman/listinfo/beginners
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.haskell.org/pipermail/beginners/attachments/20130916/d322226a/attachment.htm>