Path: utzoo!utgpu!news-server.csri.toronto.edu!rutgers!cs.utexas.edu!uunet!sci34hub!sci!dc
From: dc@sci.UUCP (D. C. Sessions)
Newsgroups: comp.lang.misc
Subject: Re: A very brief history of optimal sorting methods
Summary: Sorting methods ... Can we kill this?
Message-ID: <855@mgt3.sci.UUCP>
Date: 23 Nov 90 19:32:46 GMT
References: <5488@lanl.gov> <6913:Nov1008:23:5690@kramden.acf.nyu.edu> <16709:Nov1113:56:2390@kramden.acf.nyu.edu> <237@smds.UUCP> <RANG.90Nov18150047@nexus.cs.wisc.edu>
Reply-To: dc@mgt3.sci.com (D. C. Sessions)
Organization: SCI Technology, Inc., Huntsville, Al.
Lines: 45

In article <RANG.90Nov18150047@nexus.cs.wisc.edu> rang@cs.wisc.edu (Anton Rang) writes:
>Arrggh.  I know I'm going to regret getting into this thread.

  Amen, Brother!  Here's another self-destructive fool.

>Am I missing something here?  The original messages aren't on my news
>system any more.  Is there an explanation of the algorithm being
>discussed published somewhere?
>
>	Anton

  This whole ****ing contest has gone on long enough.  DB apparently
  understands the difference between CS and the brainless fools who often 
  escape from school with CS degrees (or so I gather from correspondence).  
  As it happens, every analysis of algorithms text I have ever seen (says 
  another CS, hopefully not a brainless fool) makes it quite clear what the 
  limits are of the O(n lg n) theorem are.  In particular, it applies only 
  to sorts based on BINARY COMPARISONS.

  The proof is almost trivial.  Since there are N! ways to arrange a list 
  of N distinct keys, any particular (ie, sorted) list must be chosen from 
  N! alternatives; this requires lg(N!) bits of information.  By Sterling's 
  approximation, this is on the order of (n lg n).  A binary comparison 
  sort returns only one bit per comparison, so O(n lg n) comparisons are 
  needed.  QED.

  DB is quite right in that if you have operators which return more than 
  one bit per operation, the process can be expedited by a similar factor.
  If a given operation returns more than lg(n) bits of information, the
  acceleration stops at linear.  Obviously, a radix M index returns lg(M)
  bits.  BTW: note that for some problems binary is the best you can 
  possibly do, since the keys are not necessarily scalar (graph relations 
  come to mind).

  Since this thread has no great relevance to LANGUAGES, I would suggest 
  that everyone who has been clogging the net with it go read a 
  junior-level algorithms text.  After that, if you want to know how good a 
  sort algorithm is, just calculate how much your main loop reduced the 
  entropy of the list in each pass.

-- 
| The above opinions may not be original, but they are mine and mine alone. |
|            "While it may not be for you to complete the task,             |
|                 neither are you free to refrain from it."                 |
+-=-=-    (I wish this _was_ original!)        D. C. Sessions          -=-=-+