Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!watmath!clyde!cbatt!ihnp4!qantel!intelca!oliveb!hplabs!tektronix!uw-beaver!cornell!gvax!jqj
From: jqj@gvax.cs.cornell.edu (J Q Johnson)
Newsgroups: net.arch
Subject: Re: One really good use for BIG core memory
Message-ID: <523@gvax.cs.cornell.edu>
Date: Sat, 27-Sep-86 05:26:05 EDT
Article-I.D.: gvax.523
Posted: Sat Sep 27 05:26:05 1986
Date-Received: Tue, 30-Sep-86 06:21:51 EDT
References: <600@sdcc12.UUCP>
Reply-To: jqj@gvax.cs.cornell.edu (J Q Johnson)
Organization: Cornell Univ. CS Dept, Ithaca NY
Lines: 22

wa263@sdcc12.UUCP proposes using large memories to obtain an O(n) sort
by using the obvious open-addressing approach.  Although I think his
general conclusion is valid:  that there are many places where space/
time tradeoffs exist in algorithms, the particular case of open address
sorting is not a very good example.

Note that your O(n) addressing-sort is successful only if the set is
dense.  Consider sorting a list of n personal names and addresses.
Presumably, n<4e10, since we have a bound based on the number of people
in the world, but the data requires, say 60 chars to represent it so
you need perhaps 300 bits of address, or 1e60 cells.  You scan phase is
NOT O(n), but rather O(2^keysize).

Conclusion:  rating sorting algorithms on their space and time
requirements as a function only of n (# of elements to be sorted) is
faulty; algorithms should be compared based on looking at their
performance bases on both n and keysize.


Incidentally, there ARE of course sorting algorithms that do better than
O(n*log n) on time performance and don't fall into the keysize trap as
deeply.  Consider all those radix sorts...