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