[H-GEN] Mergesort

[Andrae Muys]

[ Humbug *General* list - semi-serious discussions about Humbug and ]
[ Unix-related topics.  Please observe the list's charter.          ]

On Mon, 31 Jul 2000, Raymond Smith wrote:

> George has the right idea, but the recursion may not be clear. The
> algorithm is
> 
> 	// this pseudo code is almost certainly wrong!
> 	mergesort(l){
> 		if(length(l) > 2)
> 			(l1, l2) = split(l) // split in half
> 			return merge(mergesort(l1), mergesort(l2))
> 		} else {
> 			// return list if length 1
> 			// swap 'biggest' and 'smallest' if 2	
> 		}
> 	}
> 
Never did like recursive algorthms that much, although they are elegant,
easy to code, and this one is unlikely to use much stack (logn/2+1 to be
precise :).

// I expect fenceposts abound here.  Assumes arraysize is power of 2.
for (step = 1; step < arraysize; step*=2) {
	for (start = 0; start < arraysize; start+=2*step) {
		merge(list(start, step), list(start+step, start+2*step));
	}
}

The inner loop will have to be changed to handle arrays that aren't a
power of 2 long, but it's a start.  Note that all multiplication is done
by powers of 2 so leftshifts will suffice.  I'd expect the list
constructor to be inlined, and I'm not satisfied that I haven't got an
fencepost error there.

Andrae

--
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Andrae Muys <andrae at humbug.org.au> "Never ascribe to malice that which is
Shortech International Ltd          adequately explained by incompetence."
                                                     -Napoleon Bonaparte


--
* This is list (humbug) general handled by majordomo at lists.humbug.org.au .
* Postings to this list are only accepted from subscribed addresses of
* lists 'general' or 'general-post'.