Sorting.fs

module MergeSort = 
  let rec sort listToSort =
    let rec merge lhs rhs =
      match (lhs, rhs) with 
      | [], [] -> []
      | l, [] -> l
      | [], r -> r
      | x::xs, y::ys -> if x < y then x :: (merge xs rhs) else y :: (merge lhs ys)

    match listToSort with
    | [] -> []
    | [_] -> listToSort
    | _ -> 
      let split = listToSort|> List.splitAt ( (listToSort |> List.length) / 2)
      let sortedLhs = sort (fst split)
      let sortedRhs = sort (snd split)
      merge sortedLhs sortedRhs

module QuickSort =
  let rec sort listToSort = 
    match listToSort with
    | [] -> []
    | hd :: tail ->
      let less,  grt = tail |> List.partition ((>) hd)
      sort less @ (hd :: sort grt)