Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!watnot!watmath!clyde!rutgers!mit-eddie!genrad!decvax!decwrl!labrea!figaro!asente
From: asente@figaro.UUCP
Newsgroups: comp.edu,comp.lang.misc,sci.research
Subject: Re: Information on order(N) sort
Message-ID: <280@figaro.STANFORD.EDU>
Date: Tue, 24-Feb-87 13:58:06 EST
Article-I.D.: figaro.280
Posted: Tue Feb 24 13:58:06 1987
Date-Received: Fri, 27-Feb-87 04:39:38 EST
References: <814@fmsrl7.UUCP>
Reply-To: asente@figaro.UUCP (Paul Asente)
Distribution: world
Organization: Stanford University CIS Apple Orchard
Lines: 34
Keywords: sort, publish, papers, help
Xref: utgpu comp.edu:111 comp.lang.misc:279 sci.research:50

In article <814@fmsrl7.UUCP> wayne@fmsrl7.UUCP (Michael R. Wayne) writes:
>	I need information on how to share a discovery with others in
>the computer science profession.  I have an algorithm which implements
>an order(N) sort (ie the search time is linear with respect to the
>number of items with a constant overhead).  I seem to remember that
>someone "proved" that this could not be done and I do not have any
>information handy on this.

See Knuth, "The Art of Computer Programming," Volume 3, "Sorting and
Searching," page 183 ff.

To summarize, he gives a proof that in both the best worst case and
the average case you can't do better than lg n!, which is approximately
equal to n lg n.  The conditions are that each permutation of the
data is equally likely and that ***the sorting is being done by
comparisons***.  This is very important.  In earlier chapters he
gives examples of sorting methods that don't use comparisons and
work more quickly; unfortunately these only work for specialized
cases.

>Additional info:
>	In order to implement the sort, the key must be completely
>	specified.  This means that the sort is data dependent
>	Examples of complete key specification:
>		9 digits (ie SS#)
>		20-80 ASCII characters
>	Does this invalidate the algorithm?

It sounds from this as if you've just rediscovered radix sort.  See
section 5.2.5 of the above book.  If you know what the data you're
going to be sorting is you can write a radix sort that runs in O(n)
time.  Unfortunately you have to rewrite the sort for different data.

	-paul asente