Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!watnot!watmath!clyde!cbatt!ihnp4!ptsfa!lll-lcc!styx!ames!ucbcad!ucbvax!decvax!decwrl!pyramid!prls!philabs!pwa-b!mmintl!franka
From: franka@mmintl.UUCP
Newsgroups: comp.edu,comp.lang.misc,comp.os.misc
Subject: Re: Information on order(N) sort
Message-ID: <2013@mmintl.UUCP>
Date: Fri, 27-Feb-87 13:18:56 EST
Article-I.D.: mmintl.2013
Posted: Fri Feb 27 13:18:56 1987
Date-Received: Mon, 2-Mar-87 20:48:40 EST
References: <814@fmsrl7.UUCP> <175@ucdavis.UUCP> <9638@topaz.RUTGERS.EDU>
Reply-To: franka@mmintl.UUCP (Frank Adams)
Organization: Multimate International, E. Hartford, CT
Lines: 22
Keywords: sort, publish, papers, help
Xref: utgpu comp.edu:129 comp.lang.misc:309 comp.os.misc:44

In article <9638@topaz.RUTGERS.EDU> hedrick@topaz.UUCP writes:
>
>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.

Of course, the same argument is applicable to comparison-based sorting.
Comparing two keys takes time on the order of the amount of the keys which
matches.  It is true that comparing two randomly distributed keys takes, on
average in the limit, constant time; but the comparisons in a sort are not
randomly selected.  In fact, nearby keys are always compared more often
than more distant keys.  I suspect that, with key sizes determined as above
and realistic estimates of key comparison time, any comparison sort requires
O(n (log n)^2).  I don't off hand see any way to prove this; I haven't tried
very hard.

Frank Adams                           ihnp4!philabs!pwa-b!mmintl!franka
Ashton-Tate          52 Oakland Ave North         E. Hartford, CT 06108