Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!udel!haven!adm!cmcl2!lanl!jlg
From: jlg@lanl.gov (Jim Giles)
Newsgroups: comp.lang.misc
Subject: Re: A very brief history of optimal sorting methods
Message-ID: <6082@lanl.gov>
Date: 15 Nov 90 23:16:23 GMT
References: <8420:Nov1522:11:2290@kramden.acf.nyu.edu>
Organization: Los Alamos Natl Lab, Los Alamos, N.M.
Lines: 124

From article <8420:Nov1522:11:2290@kramden.acf.nyu.edu>, by brnstnd@kramden.acf.nyu.edu (Dan Bernstein):
> In article <6056@lanl.gov> jlg@lanl.gov (Jim Giles) writes:
> [...]
> 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.

You can only rest your case if (as I said previously) the paper
you cite _didn't_ explicitly mention that the time was quoted per
_byte_ of the keys.  If the paper quoted speeds in this way _without_
an explicit caveat, _then_ you have made a valid point.  Otherwise,
the paper has _no_ relevance to your claim that sorting speeds are
given in the same terms that _you_ originally did.

> [...]
> 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.

Do they? Or do they also follow the convention that I claim is the
universal: to quote speeds as a function of the number of _keys_ and
(maybe) also in other terms - but _only_ after _explicitly_ stating
what those other terms are?  I suspect the latter.  I've been informed
that the specific paper you mentioned _does_ do this.

> [...]
> Give up while you're only this far behind.

Again, extremely good advice for _you_ to take.

> [...]                            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.

Yes, the convention extablished of giving the speed in terms of
bytes AFTER explicitly stating that they were going to do so.

> [...]
> 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).

AGAIN?!?!?  The _last_ time you accused me of lying, I only had to
look back _TWO_DAYS_ to prove that you _had_ made the statement that
I attributed to you.  I have not yet recieved an apology for your
previous unfounded accusations.

In this case, the claim that you made is over a week old and has
been discarded (I only same the parts of your messages that I quote
in my responses).  However, what "we will all know" is what everyone
remembers: you _did_ claim your sort was linear _without_ saying
that you were using the non-standard measure of the number of bytes.
You corrected that to say the number of bytes _after_ several
people (including myself) took issue with your claim.  If anyone
has a longer archive of this newsgroup that I do, they will catch
you with it.

In the meantime, it's not worth pursuing since I don't even get
an apology.  The technical point has been settled anyway: your
claim to be linear used different units than everyone _expects_.
It should be noted that bubble sort is linear with the number of
_compares_ it does.  Changing the unit of measure can make just
about _anything_ linear.

> [...]
> 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.

Depends on the benchmark.  For the _overwhelming_ majority of sorting
tasks, radix sort is _not_ optimal.  Only in the domain of sorting
text lines and similar applications does radix sort really shine.
Again, read your Knuth (or any other good sorting text).  Radix is
_not_ a universal solution to sorting problems.

>   [ Knuth's chapter on sorting ]
> [...]
> 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.

And, since he is somewhat more intelligent than I am, I suspect he
completely ignored you (as I should have done).

>> > [...]                                                  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.

Same here.  But with the additional caveat that _you_ never even
admit to having _said_ the things that you get wrong.  You change
your arguments, the units of measurement, or the context of the
discussion and then claim to have been right all along.  When it
is _proven_ that your accusations of _lying_ are completely
unfounded, you refuse to even admit it (in fact, you don't respond
at all).

> [...]
>> 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.

1.) UNIX does asynchronous I/O automatically on output.
2.) UNIX has a reconnect capability (to jobs started by another tty session).
...
N-1.) The _compiler_ can detect all interprocedural aliasing.
VERY_LARGE_N.) Fortran doesn't have independent compilation.

These are examples of positions you've held in just the last year.
Practically _every_ discussion I've _had_ with you, you've been wrong.
Further, you've _never_once_ admitted to being wrong.  You've been
_VERY_ insulting as often as the opportunity presented itself.

Finally, the discussion _would_ be much more pleasant (and more
productive) if you'd leave the invective _out_!

J. Giles