[plt-scheme] Mergesort - HTDP 26.1.2

wooks




>From: "Carl Eastlund" <cce at ccs.neu.edu>
>To: "wooks ." <wookiz at hotmail.com>
>CC: plt-scheme at list.cs.brown.edu
>Subject: Re: [plt-scheme] Mergesort - HTDP 26.1.2
>Date: Wed, 26 Jul 2006 00:49:01 -0400
>
>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

No I didn't mean to compare it quicksort. Traditionally (or at least in my 
limited experience) mergesort algorithms proceed as depicted in this diagram

http://www-unix.mcs.anl.gov/dbpp/text/node127.html

the difference is that singles are derived by repeatedly halving the input 
rather than immediately slicing into singles a la HTDP (so my initial 
description of the process as being the reverse is somewhat off).

The point of going to the effort of writing a mergesort is to achieve an O n 
log n (now prudence demands that I point out that Analysis of Algorithms was 
  my weakest classes last academic year) and I always thought that the log n 
bit of that came from the way the input was split. Speaking entirely 
intuitively (which about sums up my asymptotic competence) doesn't the HTDP 
split result in a O n squared algorithm (which defeats the asymptotic 
objective - albeit it may serve the pedagogic one).