(* Sort a list of integers. *)
fun mergeSort nil = nil
|   mergeSort [e] = [e]
|   mergeSort theList =
      let
        (* From the given list make a pair of lists 
         * (x, y), where half the elements of the 
         * original are in x and half are in y. *)
        fun halve nil = (nil, nil)
        |   halve [a] = ([a], nil)
        |   halve (a :: b :: cs) =
              let
                val (x, y) = halve cs
              in
                (a :: x, b :: y)
              end;

        (* Merge two sorted lists of integers into
         * a single sorted list. *)
        fun merge (nil, ys) = ys
        |   merge (xs, nil) = xs
        |   merge (x :: xs, y :: ys) =
              if (x < y) then x :: merge(xs, y :: ys)
              else y :: merge(x :: xs, ys);

        val (x, y) = halve theList
      in
        merge(mergeSort x, mergeSort y)
      end;