[plt-scheme] Mergesort - HTDP 26.1.2

On 7/25/06, wooks . <wookiz at hotmail.com> 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.

The analysis of the asymptotic time complexity of mergesort does come
out similar to, but not the same as, quicksort.  Quicksort starts out
with one list, and at each step performs a linear partition and recurs
on twice as many lists.  Mergesort starts out with N lists, and at
each step performs a linear merge and recurs on half as many lists.
In this sense the two are direct opposites.

The difference between the two is the depth of recursion.  Quicksort's
depth depends on how close each partition comes to splitting the list
in half.  Mergesort, on the other hand, always precisely doubles each
list's size.  So quicksort can perform worse than mergesort in some
cases, because quicksort does not always progress from size N to size
1 as quickly as mergesort progresses from size 1 to size N.

This can be analyzed in more detail, with precise bounds on how fast
and slow each algorithm can be, but that sums up the intuition.

-- 
Carl Eastlund