[plt-scheme] Mergesort - HTDP 26.1.2

From: wooks . (wookiz at hotmail.com)
Date: Wed Jul 26 06:04:41 EDT 2006


>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 
>>to the more traditional top down one that proceeds by repeatedly halving 
>>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


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

Posted on the users mailing list.