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

structure Sort :> SORT =
struct
  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 (_ : 'a * 'a -> order) ([] : 'a list) : 'a list = []
    | sort _ [x] = [x]
    | sort cmp l =
        let
          val n = length l
          val half1 = List.take (l, n div 2)
          val half2 = List.drop (l, n div 2)
        in merge cmp (sort cmp half1) (sort cmp half2)
        end
end