signature SORT =
sig
  val sort : ('a * 'a -> order) -> 'a list -> 'a list
end

structure Sort :> SORT =
struct
  fun split (l : 'a list, n : int) : ('a list * int) * ('a list * int) =
    let val h = n div 2
    in ((l, h), (List.drop (l, h), n - h))
    end

  fun merge (_ : 'a * 'a -> order) ([] : 'a list) (l2 : 'a list) : 'a list = l2
    | merge _ l1 [] = l1
    | merge cmp (xl as x :: xs) (yl as y :: ys) =
        (case cmp (x, y) of
          GREATER => y :: merge cmp xl ys
        | _ => x :: merge cmp xs yl)

  fun sort' (cmp : 'a * 'a -> order) (s as (l : 'a list, n : int)) : 'a list =
    if n < 2 then List.take (l, n) else
    let
      val (first, second) = split s
      val firstSorted = sort' cmp first
      val secondSorted = sort' cmp second
    in merge cmp firstSorted secondSorted
    end

  fun sort (cmp : 'a * 'a -> order) (l : 'a list) : 'a list = sort' cmp (l, length l)
end