Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!watnot!watmath!clyde!ima!mirror!datacube!stephen
From: stephen@datacube.UUCP
Newsgroups: comp.lang.misc
Subject: Re: Information on order(N) sort
Message-ID: <103100001@datacube>
Date: Thu, 26-Feb-87 12:44:00 EST
Article-I.D.: datacube.103100001
Posted: Thu Feb 26 12:44:00 1987
Date-Received: Sun, 1-Mar-87 07:51:42 EST
References: <814@fmsrl7.UUCP>
Lines: 18
Nf-ID: #R:fmsrl7.UUCP:-81400:datacube:103100001:000:982
Nf-From: datacube.UUCP!stephen    Feb 26 12:44:00 1987


> 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.
> Of course people often use larger fields than they really need to
> number the set of items that they have, which is why the thing looks
> constant.  But in the long run as you increase the number of items
> being sorted you're going to have to increase the size of the field.

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


Stephen Watkins                    UUCP: ihnp4!datacube!stephen
Datacube Inc.; 4 Dearborn Rd.; Peabody, Ma. 01960; 617-535-6644