Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!watnot!watmath!clyde!rutgers!husc6!seismo!ll-xn!ames!amdahl!meccts!viper!dave
From: dave@viper.UUCP
Newsgroups: comp.edu,comp.lang.misc,comp.os.misc,sci.research
Subject: Re: Information on order(N) sort
Message-ID: <590@viper.UUCP>
Date: Wed, 25-Feb-87 13:49:48 EST
Article-I.D.: viper.590
Posted: Wed Feb 25 13:49:48 1987
Date-Received: Sat, 28-Feb-87 06:25:30 EST
References: <814@fmsrl7.UUCP>
Reply-To: dave@viper.UUCP (David Messer)
Distribution: world
Organization: Lynx Data Systems, Minneapolis, MN
Lines: 43
Keywords: sort, publish, papers, help
Xref: utgpu comp.edu:118 comp.lang.misc:285 comp.os.misc:33 sci.research:53

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.
 
When sorting is done by binary comparisons, it is limited
to O(N log(N)).  I bet you are using one of the methods
that doesn't use comparisons.

 >	1)  Could someone point me to the this "proof" so that I can
 >	refute it.  I think I know which part would be invalid but I
 >	would like to make sure.  Mail containing the proof would be
 >	great.

If you can refute it, then you really have something.  It
is a pretty simple proof.  Perhaps you should go into the
perpetual-motion machine business.  :-)

 >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?
 >	Of course, the sort time IS dependent on the size of the key
 >	(After all, how can a 5 character key and a 5000 character
 >	key take the same amount of time to compare?

Aha!  What you got here is the radix sort I'll bet.  Does it
work by scanning each key digit in turn (starting at the LSB)
so that, after pass X, the file is sorted on the last X digits?

That algorithm has been known for a LONG time.  The old
fashioned mechanical card-sorters used this algorithm.
-- 
                      | David Messer - Lynx Data Systems
If you can't convince |   amdahl  \
them, confuse them.   |   ihnp4   --!-- dayton --!viper!dave
   -- Harry S. Truman |   rutgers /   \ meccts /