fun merge(nil,M) = M
     |   merge(L,nil) = L
     |   merge(L as x::xs, M as y::ys) =
             if x<y then x::merge(xs,M)
             else y::merge(L,ys);

     fun split(nil) = (nil,nil)
     |   split([a]) = ([a],nil)
     |   split(a::b::cs) =
             let
                 val (M,N) = split(cs)
             in
                 (a::M, b::N)
             end;

     fun mergeSort(nil) = nil
     |   mergeSort([a]) = [a]
     |   mergeSort(L) =
             let
                 val (M,N) = split(L);
                 val M = mergeSort(M);
                 val N = mergeSort(N)
             in
                 merge(M,N)
             end;