CODEWITHSUNDEEP
f#mergesort
JimBob101
JimBob101

Reputation: 173

Merge sort for f sharp

This is my code, when I enter a very large number I get stack overflow error does anyone know why? When i enter a very large number i get that error and im not really sure what is causing it, it is only with large numbers small ones work fine.....

//
// merge two sorted lists into one:
//
let rec merge L1 L2 = 
  if L1 = [] && L2 = [] then
    []
  else if L1 = [] then
    L2
  else if L2 = [] then
    L1
  else if L1.Head <= L2.Head then
    L1.Head :: merge L1.Tail L2
  else
    L2.Head :: merge L1 L2.Tail

//
// mergesort:
//
let rec mergesort L = 
  match L with
 | []    -> []
 | E::[] -> L
 | _     -> 
   let mid = List.length L / 2
   let (L1, L2) = List.splitAt mid L
   merge (mergesort L1) (mergesort L2)

Upvotes: 3

Views: 2003

Answers (2)

Random Dev
Random Dev

Reputation: 52280

In both your functions you had the problem, that the last step you take is not the recursive call but some other thing:

  • in merge it is the :: operation
  • in mergesort it is the merge

So you have to get to a point where the very last thing is the recursive call!

One possibility in situations where you have more than one recursive call to make is to use continuations - the idea is to pass a function around that should be called with the result of the current step and then continue the computation from there.

this is a tail-recursive version of mergesort using this technique:

let mergesort xs = 
    let rec msort xs cont = 
        match xs with
        | []    -> cont []
        | [x]   -> cont xs
        | _     -> 
            let mid = List.length xs / 2
            let (xs', xs'') = List.splitAt mid xs
            msort xs' (fun ys' -> msort xs'' (fun ys'' -> cont (merge ys' ys'')))
    msort xs id

as you can see the idea is not to hard - instead of first calling both recursive paths it starts with just one half but adds a continuation that basically says:

once I have the result of mergesort xs' I take the result ys' and continue by mergesorting xs'' and then merge those

of course the second step is done in just the same way (push the merge into the continuation)

the very first continuation is usually the identity as you can see in the very last line ;)

and here is something similar for your merge:

let merge xs ys = 
    let rec mrg xs ys cont =
        match (xs, ys) with
        | ([], ys) -> cont ys
        | (xs, []) -> cont xs
        | (x::xs', y::ys') ->
            if x < y 
            then mrg xs' ys (fun rs -> cont (x::rs))
            else mrg xs ys' (fun rs -> cont (y::rs))
    mrg xs ys id

those will of course take as much space on the heap (probably more) - but that is usually no problem - your stack should be fine ;)

Upvotes: 7

Tony Lee
Tony Lee

Reputation: 5632

Each recursive call requires stack space. The more times mergesort calls itself, the more stack is used.

You avoid the stack overflow with recursive function by taking advantage of tail recursion. It simply means the last thing a function does is call itself, the call is removed and turns into a jump instead, saving stack space.

This is tricky to do in your case because you have to call mergesort twice. Only one of them can be last. The solution is to use a continuation. You only call mergesort once, but pass it a function to call, which will call mergesort the second time.

Search the internet for F# examples of a merge sort that uses continuations.

Upvotes: 3

Related Questions