Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!seismo!cmcl2!lanl!jlg
From: jlg@lanl.ARPA (Jim Giles)
Newsgroups: net.arch
Subject: Re: One really good use for BIG core memory
Message-ID: <7960@lanl.ARPA>
Date: Thu, 25-Sep-86 13:43:15 EDT
Article-I.D.: lanl.7960
Posted: Thu Sep 25 13:43:15 1986
Date-Received: Fri, 26-Sep-86 00:55:51 EDT
References: <600@sdcc12.UUCP>
Reply-To: jlg@a.UUCP (Jim Giles)
Organization: Los Alamos National Laboratory
Lines: 19

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

This algorithm is O(k) not O(n).  If you want to sort 10^6 elements (about
2^20) and each element was a 32 bit integer, the algorithm would be 2^12
times as slow as an O(n).  Of course you could map the integers into a 20
bit address and then sort the mapped data, but this is hashing.  Now you
have to worry about collisions, efficiency of the hash function, etc.  In
general, quicksort would be faster than the direct O(k) sort.

J. Giles
Los Alamos