How to implement mergesort using F#

I need to implement merge-sort using F#, For that, I need 2 auxiliary functions: split and merge, where "split" splits a list in two smaller lists whose size differ by at most 1. I' m trying to create the split function. Here is the merge and split function I implemented so far:

let rec merge (l: 'a list, m: 'a list)=
    match l,m with
    |[],[] -> []
    |[],mi::mf -> mi::mf
    |li::lf,[] -> li::lf
    |li::lf, mi::mf -> if li<mi then li::merge (lf,mi::mf)
                       else mi::merge(li::lf,mf)


   let split (l: 'a list)=
        let n= l.Length
        if n%2=1 then
            for i in  1..n/2 do

let rec mergesort (l :'a list)=
    let (left,right)=split l
    if left.Length>1 || right.Length>1 then 
        merge(mergesort left,mergesort right)
    else
        merge(left,right)

I'm stuck, I don't know how to use pattern matching to go through the list to complete the split function. I also am not sure if mergesort is correct given that split and merge is correct.

Additionally, In my partern matching cases, the list is eigher [] or ai::af So I'm a bit unsure, when we write ai::afto represent a list, is a1 equals to af if the list contains only one element?

Solution

This is how a naive mergesortimplementation may look like:

let split list =
    let rec aux l acc1 acc2 =
        match l with
            | [] -> (acc1,acc2)
            | [x] -> (x::acc1,acc2)
            | x::y::tail ->
                aux tail (x::acc1) (y::acc2)
    in aux list [] []

let rec merge l1 l2 = // this version is NOT tail-recursive
    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

let rec mergesort list = 
    match list with
        | [] -> []
        | [x] -> [x]
        | _ -> let (l1,l2) = split list
               in merge (mergesort l1) (mergesort l2)

Well-thought accurate pattern matching is the core of it.

The main part mergesort recursively applies splitting of lists of length more, than 1, and then merges splitted halves being sorted by self-application:

for an empty argument, or a singleton it just echoes it as the result
otherwise (last case of the pattern match) it uses split to halve the argument list into a tuple of "halves" lists (l1,l2) and then uses merge to combine the results of self-application to l1 and l2.

split uses the auxiliary function aux that converts any list into a tuple of lists consisting of the same elements with lengths differing no more, than by 1.

Finally, merge (implemented above in straightforward, but apparently not tail-recursive manner) reassembles together the pair of lists performing the sorting per se. It uses combining arguments into a tuple internally to simplify the argument pattern matching to just 3 cases: non-empty,empty, empty,non-empty, and non-empty,non-empty.

It is not too difficult to make merge tail-recursive, I didn't do it for didactical reasons. You may find the tail-recursive version in this gist.