functor MERGE (type Item val < : Item * Item -> bool)=
struct
local
    fun merge (a :: x) (b :: y) =
        if a < b then a :: merge x (b :: y)
        else b :: merge (a :: x) y
    |   merge x [] = x
    |   merge [] y = y ;

    fun carry []     x     = x
      | carry x      []    = [x]
      | carry x ([] :: aa) =  x :: aa
      | carry x  (a :: aa) = [] :: carry (merge x a) aa

    fun flatten []  = []
      | flatten [h] = h
      | flatten (h :: k :: t) = flatten(merge h k :: t)

    fun sorting [] = []
      | sorting (h :: t) = carry [h] (sorting t)
in 
    fun ksort x = flatten (sorting x)
end
end;