🚀 go-pugleaf

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