[H-GEN] Mergesort

[Raymond Smith]

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

On Mon, 31 Jul 2000, George Bouratsias wrote:
> Merge sort is basically, get a list of numbers split them into 2 lists
> until you have only 2 elements then compare them sort them in
> appropriate order, then merge all the lists back.

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	
		}
	}

There are lots of optimisations. For example, you might break it up into
1000 unit blocks and then do a quicksort, or you might choose a random
point for the split (rather than split in half.

Have a look at _An Introduction to Algorithims_ by Cormen et al, published
by MIT press.

Cheers,

Raymond

---
raymond at humbug.org.au                     All that we see, or seem,
                                    Is but a dream, within a dream.


--
* 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'.