(* The specifications are on the slides! *)

load "List" ;

fun split L =
  let
     val t = (length L) div 2
  in
     (List.take (L,t), List.drop (L,t))
  end

fun merge [] M = M
  | merge L [] = L
  | merge (L as x::xs) (M as y::ys) =
       if x < y then
           x :: merge xs M
       else
           y :: merge L ys

fun sort [] = []
  | sort [x] = [x]
  | sort xs =
       let
          val (ys,zs) = split xs
       in
          merge (sort ys) (sort zs)
       end


fun partition (p,[]) = ([],[])
  | partition (p,x::xs) =
       let
          val (S,B) = partition (p,xs)
       in
          if x < p then
              (x::S,B)
          else
              (S,x::B)
       end

fun sort1 [] = []
  | sort1 (x::xs) =
       let
          val (S,B) = partition (x,xs)
       in
          (sort1 S) @ (x :: (sort1 B))
       end


local
  fun sort' [] A = A
    | sort' (x::xs) A =
         let
            val (S,B) = partition (x,xs)
         in
            sort' S (x :: (sort' B A))
         end
in
  fun sort2 L = sort' L []
end