functor OKSORT (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 revs [] a = a
      | revs (h :: t) a = revs t (h :: a)

    fun runup(up, x :: y :: t) = 
        if y < x then (revs up [x], y :: t)
                 else runup(x :: up, y :: t) 
      | runup(up, xs) = (revs up xs, [])
  
    fun rundown(down, x :: y :: t) = 
        if x < y then (x :: down, y :: t)
                 else rundown(x :: down, y :: t) 
      | rundown(down, xs) = (xs @ down, [])

    fun sorting (x :: y :: t) = 
        let val (h, t') = (if x < y then runup else rundown) ([x], y :: t)
        in carry h (sorting t') end
      | sorting x = [x]
in 
    fun oksort x = flatten (sorting x)
end
end;