Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!lll-crg!topaz!ll-xn!mit-amt!mit-eddie!genrad!decvax!ittatc!dcdwest!sdcsvax!sdcc6!sdcc12!wa263
From: wa263@sdcc12.UUCP (bookmark)
Newsgroups: net.arch
Subject: One really good use for BIG core memory
Message-ID: <600@sdcc12.UUCP>
Date: Mon, 22-Sep-86 23:50:07 EDT
Article-I.D.: sdcc12.600
Posted: Mon Sep 22 23:50:07 1986
Date-Received: Wed, 24-Sep-86 05:08:32 EDT
Organization: You See Sandy Eggo
Lines: 30

<--- bug snack

	I know one really good use for a BIG core memory.  There is a
simple O(n) sorting algorithm... suppose we want to sort n elements with
keys ranging in value from 1 to k (k >= n).  Just get a big array
of k slots, mark them all with some illegal value, then copy
each of the items to be sorted into the appropriate (k'th) place in the
array (this is called an "address calculation" sort).  Then scan the array
through and copy out the items in order.  The sort phase is O(n), and the
scan phase takes about constant+(n*otherconst) time, so the whole thing is O(n).

	(Obviously, this simple scheme doesn't deal with multiple items 
having the same key... but there are a variety of simple fixes for that.
If the item is big, so you don't want to copy it, you can just copy
a pointer to it, or its index in the source array, or whatever.  Please...
don't bother posting (or mailing) anything about similar quibbles--if you
can think of a quibble and its solution in less than five minutes,
so can everyone else including me.)

	Now, this is a great sorting scheme.  The reason we worry
all the time about neat things like Quicksort, or some of the time about
horrors like twelve-tape polyphase merge sorts, is because we often don't
have enough memory to do a sort in the simple way detailed above.  However,
the more core you give me, the more able I'll be to use algorithms like this
sorting scheme that trade size for speed-- and the faster my programs will run.


					bookmark@sdcsvax.ARPA

				   ...!sdcsvax!bookmark