Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!watnot!watmath!clyde!rutgers!husc6!necntc!cullvax!drw
From: drw@cullvax.UUCP
Newsgroups: comp.lang.misc
Subject: Information on order(N) sort
Message-ID: <860@cullvax.UUCP>
Date: Sat, 28-Feb-87 14:22:59 EST
Article-I.D.: cullvax.860
Posted: Sat Feb 28 14:22:59 1987
Date-Received: Sun, 1-Mar-87 17:05:34 EST
Organization: Cullinet Software, Inc., Westwood, MA
Lines: 17

stephen@datacube.UUCP writes:
> This is absolutely wrong. The size of the key associated with an item
> is entirely independent of the number of bits required to address that
> item. The radix sort is O( n log M ) in time, where log M is the size
> of the key in bits. It is easy to envision sorting an array of 1 million
> 8 bit keys, in which case the algorithm would be O( 8*n ), not O(20*n).

Yeah, but you have to be able to *address* all 1 million records in
some way or another (unless you are storing them on tape!).  That
requires 20 bit addresses, minimum.  Even if your keys are small, the
addresses of the records will eventually bring in the log N factor.

Dale
-- 
Dale Worley		Cullinet Software
UUCP: ...!seismo!harvard!mit-eddie!cullvax!drw
ARPA: cullvax!drw@eddie.mit.edu