[plt-scheme] Mergesort - HTDP 26.1.2

On Jul 26, 2006, at 6:04 AM, wooks . wrote:

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

No matter how you do it, you have to go to every list/array element  
once to get started. That's O(n). From then on, the workings are the  
same. -- Matthias