merge_sort_in_f_sharp

// http://en.wikipedia.org/wiki/Merge_sort
let rec mergeSort (arr : 'a []) =
    let split (arr : _ array) =
        let n = arr.Length
        arr.[0..n/2-1], arr.[n/2..n-1]
 
    let rec merge (l : 'a array) (r : 'a array) =
        let n = l.Length + r.Length
        let res = Array.zeroCreate<'a> n
        let mutable i, j = 0, 0
        for k = 0 to n-1 do
            if i >= l.Length   then res.[k] <- r.[j]; j <- j + 1
            elif j >= r.Length then res.[k] <- l.[i]; i <- i + 1
            elif l.[i] < r.[j] then res.[k] <- l.[i]; i <- i + 1
            else res.[k] <- r.[j]; j <- j + 1
 
        res
 
    match arr with 
    | [||] | [| _ |] -> arr
    | _ -> let (x, y) = split arr
           merge (mergeSort x) (mergeSort y)