Can someone please help explain how this merge sort algorithm works?

Question

I started learning F# yesterday and am struggling a bit with all the new functional programming.

I am trying to understand this implementation of merge sort which uses a split function. The split function is defined as:

let rec split = function
    | [] -> ([], [])
    | [a] -> ([a], [])
    | a :: b :: cs -> let (r, s) = split cs
                      in (a :: r, b :: s)

The way I understand it, we take a list and return a tuple of lists, having split the list into two halves. If we pattern match on the empty list we return a tuple of empty lists, if we match on a list with one element we return a tuple with the list and an empty list, but the recursive case is eluding me.

a :: b :: cs means a prepended to b prepended to cs, right? So this is the case where the list has at least 3 elements? If so, we return two values, r and s, but I have not seen this "in" keyword used before. As far as I can tell, we prepend a, the first element, to r and b, the second element, to s, and then split on the remainder of the list, cs. But this does not appear to split the list in half to me.

Could anybody please help explain how the recursive case works? Thanks a lot.

Answer 1

You can ignore the in keyword in this case, so you can read the last case as just:

| a :: b :: cs ->
    let (r, s) = split cs
    (a :: r, b :: s)

Note that this will match any list of length 2 or greater, not 3 as you originally thought. When the list has exactly two elements, cs will be the empty list.

So what's going on in this case is:

• If the list has at least 2 elements:
  • Name the first element a
  • Name the second element b
  • Name the rest of the list cs (even if it's empty)
  • Split cs recursively, which gives us two new lists, r and s
  • Create two more new lists:
    • One with a on the front of r
    • The other with b on the front of s
  • Return the two new lists

You can see this in operation if you call the function like this:

split [] |> printfn "%A"                // [],[]
split [1] |> printfn "%A"               // [1],[]
split [1; 2] |> printfn "%A"            // [1],[2]
split [1; 2; 3] |> printfn "%A"         // [1; 3],[2]
split [1; 2; 3; 4] |> printfn "%A"      // [1; 3],[2; 4]
split [1; 2; 3; 4; 5] |> printfn "%A"   // [1; 3; 5],[2; 4]

---

Update: What exactly does in do?

The in keyword is just a way to put a let-binding inside an expression. So, for example, we could write let x = 5 in x + x, which is an expression that has the value 10. This syntax is inherited from OCaml, and is still useful when you want to write the entire expression on one line.

In modern F#, we can use whitespace/indentation instead, by replacing the in keyword with a newline. So nowadays, we would usually write this expression as follows:

let x = 5
x + x

The two forms are semantically equivalent. More details here.