[Haskell-cafe] Clarification Please

[Michael Vanier]

OK, you have the split function, and you have the merge function, and now you have to define the 
msort function.  First write down the base cases (there are two, as you mention), which should be 
obvious.  Then consider the remaining case.  Let's say you split the list into two parts.  Then what 
would you do?

Mike

PR Stanley wrote:
> I'm not sure. We start with one list and also, perhaps I should have 
> mentioned that I have a merge function which takes two sorted lists with 
> similar, now, what do they call it, similar orientation? and merges them 
> into one sorted list.
> e.g. merge [1, 4,] [2, 3]
> [1,2,3,4]
> Cheers, Paul
> At 04:02 14/09/2007, you wrote:
>> 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 
>>> Haskell:
>>> 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
>>> _______________________________________________
>>> Haskell-Cafe mailing list
>>> Haskell-Cafe at haskell.org
>>> http://www.haskell.org/mailman/listinfo/haskell-cafe 
> 
> ------------------------------------------------------------------------
> 
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe