Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!watnot!watmath!clyde!rutgers!topaz!hedrick
From: hedrick@topaz.UUCP
Newsgroups: comp.edu,comp.lang.misc,comp.os.misc
Subject: Re: Information on order(N) sort
Message-ID: <9638@topaz.RUTGERS.EDU>
Date: Wed, 25-Feb-87 19:16:11 EST
Article-I.D.: topaz.9638
Posted: Wed Feb 25 19:16:11 1987
Date-Received: Fri, 27-Feb-87 23:28:26 EST
References: <814@fmsrl7.UUCP> <175@ucdavis.UUCP>
Organization: Rutgers Univ., New Brunswick, N.J.
Lines: 7
Keywords: sort, publish, papers, help
Xref: utgpu comp.edu:114 comp.lang.misc:283 comp.os.misc:30

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.