# [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.)