regression/msort.sml

   1        fun cp [] =[]
   2          | cp (x::xs)= x :: cp xs
   3
   4        (* exormorphic merge *)
   5        fun merge(xs, []):int list = cp xs
   6          | merge([], ys) = cp ys
   7          | merge(l1 as x::xs, l2 as y::ys) =
   8                if x<y then x :: merge(xs, l2)
   9                else y :: merge(l1, ys)
  10
  11        (* splitting a list *)
  12        fun split(x::y::zs, l, r) = split(zs, x::l, y::r)
  13          | split([x], l, r) = (x::l, r)
  14          | split([], l, r) = (l, r)
  15
  16        (* exomorphic merge sort *)
  17        fun msort []  = []
  18          | msort [x] = [x]
  19          | msort xs = let val (l, r) = split(xs, [], [])
  20                       in merge(msort l, msort r)
  21                       end;