Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!utgpu!water!watnot!watmath!clyde!rutgers!seismo!rochester!pt.cs.cmu.edu!sei.cmu.edu!firth
From: firth@sei.cmu.edu.UUCP
Newsgroups: comp.edu,comp.lang.misc,comp.os.misc,sci.research
Subject: Re: Information on order(N) sort
Message-ID: <561@aw.sei.cmu.edu.sei.cmu.edu>
Date: Tue, 24-Feb-87 11:22:13 EST
Article-I.D.: aw.561
Posted: Tue Feb 24 11:22:13 1987
Date-Received: Thu, 26-Feb-87 23:33:39 EST
References: <814@fmsrl7.UUCP> <25183@rochester.ARPA>
Sender: netnews@sei.cmu.edu
Reply-To: firth@bd.sei.cmu.edu.UUCP (PUT YOUR NAME HERE)
Distribution: world
Organization: Carnegie-Mellon University, SEI, Pgh, Pa
Lines: 86
Keywords: sort, publish, papers, help
Xref: utgpu comp.edu:106 comp.lang.misc:274 comp.os.misc:25 sci.research:48

**  From: Mail Delivery Subsystem <MAILER-DAEMON@sei.cmu.edu>
**  Subject: Returned mail: User unknown

The above is my excuse for posting here a long reply that
should have gone to the author.  Please accept my apologies.

In article <814@fmsrl7.UUCP> you write:
>
>	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.  (Back in my college days, my professor
>and I did not see eye-to-eye and he threw me out of my data structures
>class.)  I really need a couple of things:
>
>	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.

Well, the proof as I learned it was quite simple, and went thus:

You are given an unordered set S of items X, of cardinality N,
and are required to order it.  You have an ordering function
"<" [X,X=>Boolean] which is guaranteed total, transitive and
antisymmetric.  That is, you may assume "x<y" computable for
all x,y in S; you may assume that x>y xor y>x, and you may
assume x<y and y<z implies x<z.

(A) Now the set N has N! possible arrangements, of which exactly
    one is correctly sorted.  

(B) Any sorting engine applied to the
    set therefore requires at least log(N!) bits of information
    to do the sort.

(C) Each comparison gives exactly one bit of information, the
    Boolean result.  Therefore, you need to make O(log(N!))
    comparisons, which is of course O(NlogN) by Stirling's
    theorem.

(D) Assuming each comparison takes a fixed time, there is therefore
    a time component of order O(NlogN) and no sort algorithm can
    do better. (Multiprocessing is cheating, but any way the product
    of processors*runtime is what counts as the cost)

Can we defeat this proof?  Let's look at the assumptions.

(A) Actually, we need a stronger assumption here - that all arrangements
    are equally likely.  Otherwise, we certainly CAN take advantage of
    partial ordering to speed up the sort.  That's one reason why a
    linear insertion sort is a good tool: even though it is O(N^2)
    in principle, it takes advantage of any ordered subsets.

(B) This one is the information-theoretic equivalent of the second
    law of thermodynamics, and you'd better believe it!  Note that
    we make no assumptions about the speed of this engine; the cost
    of the comparisons is what the proof addresses.

(C) True by hypothesis.  However, there are far better comparison
    functions than this one.  For example, simple subtraction of
    the arguments gives you more information - it tells you HOW MUCH
    bigger one is than the other.  This information can be used,
    along with knowledge of the regularity with which values are
    distributed, to improve the sort.

    In the limit of a perfectly smooth distribution, a radix
    distribution sort is O(N). 

(D) Dubious, to say the least.  For example, a hardware "find first
    bit" instruction performs the equivalent of many comparisons in
    a fixed time.  This could be used as the basis of a shellsort
    by taking a block of key values, transposing them bitwise, and
    using a chain of "find first bit" instructions to find the first
    key greater than the pivot.  I'm not saying it would be fast on
    current machines, but it would be better than O(NlogN).

Hope this helps with your first question.

Robert Firth

Postscript: sloppy presentations of the theorem tend to confuse
people on point (C) of the above four - the comparison has to
to yield a pure Boolean for the proof to work.