mergesort

let rec mergeSort f xs =
  let rec _sort left right res =
    match (left, right) with
    | ([], []) -> (res |> List.rev)
    | (ls, []) -> (res |> List.rev) @ ls
    | ([], rs) -> (res |> List.rev) @ rs
    | (l :: ls, r :: rs) ->
      if (f l r) then
        _sort ls right (l :: res)
      else
        _sort left (rs) (r :: res)

  match xs with
  | []  -> xs
  | [x] -> xs
  | _ ->
    let (ls, rs) = splitAt ((xs |> List.length) / 2) xs
    _sort (mergeSort f ls) (mergeSort f rs) []