[plt-scheme] Mergesort - HTDP 26.1.2

wooks wrote:

 >Is this mergesort algorithm given for this problem asymptotically
 >equivalent to the more traditional top down one that proceeds by 
 >repeatedly halving the input and then merging.

 >My initial gut feel was that it wasn't but thinking about it a little
 >harder, isn't it the case that we are doing the same amount of work in
 >reverse order.

It is asymptotically the same, and if the number of elements is a power 
of 2, you are in fact doing the same work in the same order, as far as 
comparisons are concerned. (It might be the same for non-powers-of-2, or 
it might be slightly different; I haven't thought about it enough.) It's 
only the code and the organization of how the comparisons are done which 
is different.

 >P.S. Was the intended output of the algorithm a nested list as opposed 
 >to a list?

You end up with a list of one element, which is a list of n elements. 
You need to wrap that in something which just extracts the list of n. --PR

(PS The version of mergesort in the Java-based textbook we use for our 
main CS2 course is in fact an O(n^2) implementation, because it tries to 
get around messiness with indices by allocating a temporary array of 
size n on each recursive call.)