Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!watmath!clyde!burl!ulysses!allegra!alice!ark
From: ark@alice.UucP (Andrew Koenig)
Newsgroups: net.arch
Subject: Re: One really good use for BIG core memory
Message-ID: <6111@alice.uUCp>
Date: Fri, 26-Sep-86 11:33:07 EDT
Article-I.D.: alice.6111
Posted: Fri Sep 26 11:33:07 1986
Date-Received: Tue, 30-Sep-86 03:24:52 EDT
References: <600@sdcc12.UUCP>
Organization: Bell Labs, Murray Hill
Lines: 15


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

Only trouble is that it's O(k), not O(n), because that's how long
it takes to scan all the way through your BIG memory.

When k is much larger than n, you can sort in O(n log(k)/R) by doing a
radix sort in radix R.