Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!lll-crg!nike!ucbcad!ucbvax!brahms!desj
From: desj@brahms.BERKELEY.EDU (David desJardins)
Newsgroups: net.arch
Subject: Re: One really good use for BIG core memory
Message-ID: <15801@ucbvax.BERKELEY.EDU>
Date: Wed, 24-Sep-86 21:55:26 EDT
Article-I.D.: ucbvax.15801
Posted: Wed Sep 24 21:55:26 1986
Date-Received: Thu, 25-Sep-86 03:43:21 EDT
References: <600@sdcc12.UUCP>
Sender: usenet@ucbvax.BERKELEY.EDU
Reply-To: desj@brahms.UUCP (David desJardins)
Organization: University of California, Berkeley
Lines: 17

In article <600@sdcc12.UUCP> wa263@sdcc12.UUCP (bookmark) writes:
>
>	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).

   The 'scan phase' takes ** O(k) ** time, not O(n).  In typical sorting
applications k >>> n.  If k ~ n, then we already have enough memory for
the size k table (if we have enough memory to quicksort the items them-
selves!).

   -- David desJardins