F# mergesort tail-recursion

Question

I tried to write a tail recursive code for mergesort. The code does compile and run. However, the output is wrong. It only outputs one integer. I was wondering how I would fix this code so that the list of integers are sorted and outputted.

let rec merge L L2 P = 
  match L, L2 with
  | [], [] -> P
  | [], _  -> L2
  | _,  [] -> L
  | hd::t1, hd2::t2 ->
    if hd <= hd2 then
       merge t1 L2 (P @ [hd])
    else
       merge L t2 (P @ [hd2])


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

Answer 1

Your problem is in function merge: imagine you sort the list [2;1]. It turns to merge [2] [1] [], then to merge [] [2] [1], and finally second case of match yields [2]. Second and third cases of match must account for P somehow.

In fact, you absolutely do not need to manipulate 3 lists in your merge, two is quite enough if we refactor it to:

let rec merge l1 l2 =
    match (l1,l2) with
    | (x,[]) -> x
    | ([],y) -> y
    | (x::tx,y::ty) ->
        if x <= y then x::merge tx l2
        else y::merge l1 ty 

and change the last line of ms to merge (ms L) (ms L2) - and this variant does work as expected:

ms List<int>.Empty returns []

ms [2;1] returns [1;2]

e.t.c

Update: As @kvb pointed out the merge function above is not tail recursive. This is correct and refactoring it to tail-recursive version requires more involvement by introducing an accumulator acc being filled via continuation function:

let merge l1 l2 =
  let rec mergeAux continuation l1 l2 = 
    match l1, l2 with
    | l1, [] -> continuation l1
    | [], l2 -> continuation l2
    | x::tx, y::ty ->
      if x <= y then mergeAux (fun acc -> continuation(x::acc)) tx l2
      else mergeAux (fun acc -> continuation(y::acc)) l1 ty
  mergeAux id l1 l2

Now the implementation is tail-recursive that is easy to check with:

let rand = System.Random() in
    List.init 1000000 (fun _ -> rand.Next(-10000,10000)) |> ms
>
val it : int list =
  [-10000; -10000; -10000; -10000; -10000; -10000; -10000; ...