Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!watnot!watmath!clyde!ima!mirror!cca!g-rh
From: g-rh@cca.UUCP
Newsgroups: comp.lang.misc
Subject: Re: Information on order(N) sort
Message-ID: <13519@cca.CCA.COM>
Date: Fri, 27-Feb-87 21:20:41 EST
Article-I.D.: cca.13519
Posted: Fri Feb 27 21:20:41 1987
Date-Received: Sun, 1-Mar-87 13:26:01 EST
References: <814@fmsrl7.UUCP> <103100001@datacube>
Reply-To: g-rh@CCA.UUCP (Richard Harter)
Organization: Computer Corp. of America, Cambridge, MA
Lines: 24

In response too:

>> Note that the more objects you have, the larger the field needed to
>> describe them.  In fact the number of bits needed to number N items is
>> log N.  So I claim that a radix sort is in some general sense N log N.
>> .... 

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

Not absolutely wrong -- the statement should be "... the more distinct
objects ...".  N distinct keys do require log(N) key lengths.  It should
also be noted comparison costs in comparison sorts will increase with
key length.  I suspect that it can be shown comparison costs must grow
as log(M) for large keys.


-- 

Richard Harter, SMDS Inc. [Disclaimers not permitted by company policy.]