Michael Vanier mvanier at cs.caltech.edu
Thu Sep 13 23:02:45 EDT 2007

```Define a merge function that merges two sorted lists into a sorted list containing all the elements
of the two lists.  Then define the msort function, which will be recursive.

Mike

PR Stanley wrote:
> Hi
> Taken from chapter 6, section 8 of the Hutton book on programming in
> 5. Using merge, define a recursive function
> msort :: (Ord a) => [a] -> [a]
> that implements merge sort, in which the empty list and singleton lists
> are already sorted, and any other list is sorted by merging together the
> two lists that result from sorting the two halves of the list separately. :
> Hint: first define a function
> ¬halve :: [a] -> [([a], [a])]
> ¬that splits a list into two halves whose length differs by at most one.
>
>     Create a halve function - okay, that's fairly straightforward. The
> rest, I'm afraid, is a little obscure. I'm not looking for the solution;
> I'd like to work that out for meself. However, I'd  really appreciate
> some clues as to the general structure of the algorithm.
> Much obliged,
> Paul
>
> _______________________________________________