title: Using continuation / CPS to implement tail-recursive MergeSort in OCaml
body: <p>I am trying to implement a <code>tail-recursive</code> <code>MergeSort</code> in <code>OCaml</code>.</p>
  
  <p>Since <code>Mergesort</code> naturally is not tail-recursive, so I am using <code>CPS</code> to implement it.</p>
  
  <p>Also my implementation is inspired by <a href="https://stackoverflow.com/questions/2529580/tail-recursive-merge-sort-in-ocaml">Tail-recursive merge sort in OCaml</a></p>
  
  <p><strong>Below is my code</strong></p>
  
  <hr>
  
  <pre><code>let merge compare_fun l1 l2 = 
    let rec mg l1 l2 acc =
      match l1, l2 with
        | ([], []) -&gt; List.rev acc
        | ([], hd2::tl2) -&gt; mg [] tl2 (hd2::acc)
        | (hd1::tl1, []) -&gt; mg tl1 [] (hd1::acc)
        | (hd1::tl1, hd2::tl2) -&gt;
           let c = compare_fun hd1 hd2
           in 
           if c = 1 then mg l1 tl2 (hd2::acc)
           else if c = 0 then mg tl1 tl2 (hd2::hd1::acc)
           else mg tl1 l2 (hd1::acc)
    in 
    mg l1 l2 [];;
  
  let split_list p l = 
    let rec split_list p (acc1, acc2) = function
      | [] -&gt; (List.rev acc1, List.rev acc2)
      | hd::tl -&gt;
        if p &gt; 0 then split_list (p-1) (hd::acc1, acc2) tl
        else split_list (p-2) (acc1, hd::acc2) tl
    in 
    split_list p ([], []) l;;
  
  let mergeSort_cps compare_fun l =
    let rec sort_cps l cf =  (*cf = continuation func*)
      match l with 
        | [] -&gt; cf []
        | hd::[] -&gt; cf [hd]
        | _ -&gt;
          let (left, right) = split_list ((List.length l)/2) l
          in 
          sort_cps left (fun leftR -&gt; sort_cps right (fun rightR -&gt; cf (merge compare_fun leftR rightR)))
    in 
    sort_cps l (fun x -&gt; x);;
  </code></pre>
  
  <hr>
  
  <p>When I compile it, and run it with a <code>1,000,000</code> <code>integers</code>, it gives the error of <code>stackoverflow</code>. <strong>Why?</strong></p>
  
  <hr>
  
  <p><strong>Edit</strong></p>
  
  <p>Here is the code I used for testing:</p>
  
  <pre><code>let compare_int x y =
    if x &gt; y then 1
    else if x = y then 0
    else -1;;
  
  let create_list n = 
    Random.self_init ();
    let rec create n' acc =
      if n' = 0 then acc
      else 
        create (n'-1) ((Random.int (n/2))::acc)
    in 
    create n [];;
  
  let l = create_list 1000000;;
  
  let sl = mergeSort_cps compare_int l;;
  </code></pre>
  
  <p>in <code>http://try.ocamlpro.com/</code>, it gave this error: <code>Exception: RangeError: Maximum call stack size exceeded.</code></p>
  
  <p>in <code>local ocaml top level</code>, it didn't have any problem</p>