CPS 206 Fall 1999, Problem 5. Work alone.

Define and test a pure Scheme function (msort L) which returns list L, sorted in non-decreasing order, when L is a list of integers. (Pure Scheme is the subset of the Scheme language that uses no function whose name ends with "!"). Several auxiliary functions will also be needed:

1. (merge L M) returns the list which results from merging sorted lists L and M.
   That is, (merge '(1 3 10) '(0 2)) is (0 1 2 3 10).
2. A function to return a list in which every element of the argument list appears alone in a sublist: (listify '(6 3 7)) is ((6) (3) (7)). Merge can then be applied to pairs of elements in (listify L), then to pairs of the sorted lists which result, until all elements of L appear in a single sorted sublist. So the list (6 3 7) first becomes ((6) (3) (7)), then ((3 6) (7)), then ((3 6 7)), and the single inner list is the desired result.
3. Functions to call select pairs of sorted sublists to be combined, using "merge", into a new list of sorted sublists, and repeat this action, until only one sublist appears in the new list.

This version of merge sort is one of the fastest Scheme versions of the algorithm. It avoids multiple examinations of the elements in L to do such things as counting them, to determine L's length, or to "split" L into nearly-equal pieces, by first selecting the leading half of L, and then selecting the second half of L.

After testing your program to be sure it works, submit a single file containing only the Scheme function definitions you need -- no test runs, please.