Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!watnot!watmath!clyde!rutgers!ames!ucbcad!ucbvax!ucdavis!deneb!cccmark
From: cccmark@deneb.UUCP
Newsgroups: comp.edu,comp.lang.misc,comp.os.misc
Subject: Re: Information on order(N) sort
Message-ID: <175@ucdavis.UUCP>
Date: Tue, 24-Feb-87 22:07:22 EST
Article-I.D.: ucdavis.175
Posted: Tue Feb 24 22:07:22 1987
Date-Received: Fri, 27-Feb-87 06:00:34 EST
References: <814@fmsrl7.UUCP>
Reply-To: cccmark@deneb.UUCP (Mark Nagel)
Distribution: world
Organization: University of California, Davis
Lines: 32
Keywords: sort, publish, papers, help
Xref: utgpu comp.edu:112 comp.lang.misc:280 comp.os.misc:28

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
...
>	3)  Has this problem already been solved?  If so, pointers to
>	this would also be appreciated (since no one I talked to knew
>	about the solution).
>
>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?

There already exist several data dependent sorts that execute at O(N).  Yours
sounds much like the radix sort.  The best that a **GENERAL** sort algorithm
can hope to achieve is O(NlogN).  This can be proved (I don't have the proof
handy) by showing that the set of all possible permutations increases
factorially and that the number of steps down the best tree is O(NlogN).  I
know, I know, this is wimpy.  Look it up in a DS text.  The point is that
you can come up with special cases where you can do better than O(NlogN),
but this invalidates nothing about general sorting algorithms.

- Mark Nagel

ucdavis!deneb!cccmark@ucbvax.berkeley.edu               (ARPA)
mdnagel@ucdavis                                         (BITNET)
...!{sdcsvax|lll-crg|ucbvax}!ucdavis!deneb!cccmark      (UUCP)