Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!yale!cmcl2!kramden.acf.nyu.edu!brnstnd
From: brnstnd@kramden.acf.nyu.edu (Dan Bernstein)
Newsgroups: comp.lang.misc
Subject: Re: A very brief history of optimal sorting methods
Message-ID: <8420:Nov1522:11:2290@kramden.acf.nyu.edu>
Date: 15 Nov 90 22:11:22 GMT
References: <5293:Nov1518:36:0490@kramden.acf.nyu.edu> <6056@lanl.gov>
Organization: IR
Lines: 94

In article <6056@lanl.gov> jlg@lanl.gov (Jim Giles) writes:
> From article <5293:Nov1518:36:0490@kramden.acf.nyu.edu>, by brnstnd@kramden.acf.nyu.edu (Dan Bernstein):
> > Please don't say anything if you don't know what you're talking about.
> A statement that applies to _you_ far more often than to me.

That accusation is not borne out by the evidence. See below.

> >> The speed of sorting techniques is _uniformly_ given by _all_
> >> the literature as a function of the number of _keys_ to be sorted,
> >> _not_ as a function of the number of bytes sorted.
> > You are wrong. Here's a counterexample: In 1987, in the article by
> > Tarjan and somebody else ``inventing'' MSD radix sort, [...]
> Oh wow!  A _single_ paper (which you can't even give a proper citation
> of) which goes against the grain of the _whole_ rest of the industry.

You are WRONG! You said ``uniformly.'' You are WRONG! You said ``all.''
You are WRONG! There is no escaping this fact. I rest my case.

In attempting to redeem yourself you imply that it is just a ``single''
paper. But you're wrong there. As I said in the article you're quoting
(but probably failed to read), the references to that paper have many
further counterexamples to your original statement.

Give up while you're only this far behind.

> > [...]                                       Less precise bounds were
> > given in terms of the number of keys under various restrictions. [...]
> So, even in your supposed counter-example paper the authors _do_
> give the speed in terms of the number of _keys_.

No; they only give some imprecise bounds, and only under various
restrictions (the keys being all distinct, the keys having this much to
distinguish between them, etc.). They give the speed in terms of the
number of bytes, as per a convention established in many previous
papers. There is no escaping this fact.

> Everyone in
> the industry will _assume_ (correctly - for all but Dan) that a quoted
> sort speen is in terms of the number of _keys_ - unless _explicitly_
> stated otherwise.  I suspect that your cited paper _does_ make such
> an explicit caveat.  _YOUR_ original claims _did_not_.

Are you implying that I have ever stated ``sorting is linear'' without
saying ``in the number of bytes''? I challenge you to prove your
accusation. If you fail, we will all know you have lied (again).

> Woopee!  It is my experience with _all_ "supposedly optimized" UNIX
> utilities that they are incredibly slow.  The fact that you can use
> a slow technique and still beat a UNIX utility is hardly a surprise.

Jim, I'll bet you can't write a sort program even half as fast as the
standard UNIX version. I challenge you (again) to write a sort program
that will beat mine, under the restriction that you use an O(n log n)
sort---which, of course, you claim is faster than radix sort.

  [ Knuth's chapter on sorting ]
> He does _not_ find (as you seem to have concluded) that _one_
> technique is _always_ the best choice.

He dismissed MSD radix sort as too much housekeeping to be worthwhile.
Furthermore, there are optimizations to MSD radix sort that he did not
consider. I have brought up ``adaptive distribution sort'' in a letter
to him.

As much as I respect Knuth, the man makes occasional misjudgments. His
statements about the asymptotic speed of multiplication, for example,
are incorrect. I hope to convince him to correct his statements about
Nussbaumer's method. Similarly, I hope to convince him that a variant of
radix sort is appropriate for an extremely wide range of applications,
and worth consideration in every application.

> >> If a whole key (like a 64-bit integer for example) can be compared in
> >> the same time as it takes to compare your little 8-bit chunk of it,
> > Radix sorts do not compare the bytes they are sorting. [...]
> Yes, I figured you'd seize on this as soon as I posted it.  I typed
> in a hurry and should have said "index with" rather than "compare."

Fine, so you admit you're wrong.

> > [...]                                                  Please don't say
> > anything if you don't know what you're talking about.
> Again, take your own advice.

I find it sickening how you post a series of incorrect statements, I
refute each of them, and now you imply that I'm the one who's off his
rocker.

> Just QUIT making insulting
> remarks about others when those _same_ remarks apply more appropriately
> to _you_.

Hasn't happened yet in my conversations with you.

---Dan