merge_sort.fsx

exception NoItems


// O(n)
let reverse lst =
  let rec rr lst acc =
    match lst with
    | [] -> acc
    | x :: xs -> rr xs (x :: acc)
  rr lst []


// O(n)
let count lst =
  let rec r_count lst acc =
    match lst with
    | [] -> acc
    | x :: xs -> r_count xs (acc + 1)
  r_count lst 0


// O(n + m)
let merge lst1 lst2 =
  let rec merge_r lst1 lst2 acc =
    match lst1 with
    | [] ->
      match lst2 with
      | [] -> acc
      | y :: ys -> merge_r lst1 ys (y :: acc)
    | x :: xs ->
      let left = x
      match lst2 with
      | [] -> merge_r xs lst2 (x :: acc)
      | y :: ys ->
        let right = y
        if left < right then
          merge_r xs lst2 (left :: acc)
        else
          merge_r lst1 ys (right :: acc)
  reverse (merge_r lst1 lst2 [])


// O(n)
let half lst =
  let rec first n lst acc =
    if n = 0 then
      acc
    else
      match lst with
      | [] -> raise NoItems
      | x :: xs -> first (n - 1) xs (x :: acc)

  let rec last n lst =
    if n = 0 then
      lst
    else
      match lst with
      | [] -> raise NoItems
      | x :: xs -> last (n - 1) xs
  let many = (count lst) / 2
  (reverse (first many lst [])), (last many lst)


// O(n * log(n))
let rec merge_sort (lst:'a list) : 'a list =
  let n = count lst
  if n = 1 then
    lst
  else
    let left, right = half lst
    let left = merge_sort left
    let right = merge_sort right
    merge left right