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: <13722:Nov1604:50:2990@kramden.acf.nyu.edu>
Date: 16 Nov 90 04:50:29 GMT
References: <8420:Nov1522:11:2290@kramden.acf.nyu.edu> <6082@lanl.gov>
Organization: IR
Lines: 103

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

This is not a game where you can change the rules. You've been making a
series of incorrect statements, and no amount of squirming and
revisionist history will make your statements correct.

I am perfectly willing to accept your point that people assume that
``sorting is linear'' refers to linearity in the number of keys. So
such a statement would only be true if the key length is fixed, not in
the general case. That's why I make sure to say ``in the number of
bytes.''

  [ whimper about how the Holy Grail has expired ]

Just name the thread and I'll send you all my articles in that thread.

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

No, I did not. If I have ever said so it can only have been in a context
where the keys were fixed-length (sorting machine integers, perhaps).
Maybe you're remembering something like that?

> If anyone
> has a longer archive of this newsgroup that I do, they will catch
> you with it.

Go for it, folks! I'd love to see the results. Come on, everybody who
thinks that I've been making incorrect statements. Lots of sites have
two-week histories.

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

See, you keep claiming this. I'll even let you pick a set of three
sorting benchmarks that an impartial judge accepts as realistic. I'm
still waiting for your response to my challenge.

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

He is a busy man, and has many letters to respond to. However, as he
owes me about $30, I expect he will write back soon.

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

It does. The meaning of asynchronous is ``not synchronous.'' There is
only one synchronous I/O (you tell the disk to run, wait for it to
complete, and then continue); there are lots of degrees of being not
synchronous. UNIX does asynchronous I/O on output.

I agree that buffering does not make I/O as asynchronous as it could be;
I thank you for helping me understand that the extra copy time is a real
burden on Crays, and hence should be eliminated if possible.

> 2.) UNIX has a reconnect capability (to jobs started by another tty session).

It does. See my pty program. UNIX has a reconnect capability.

> N-1.) The _compiler_ can detect all interprocedural aliasing.

I never said any such thing. I said that the compiler can detect a
particular type of interprocedural aliasing, which should suffice for
all the real-world problems you care about.

> VERY_LARGE_N.) Fortran doesn't have independent compilation.

I never said any such thing. I said that Fortran doesn't have
independent compilation *as in C*. I am sick of how you ignore these
qualifiers, from ``packed'' on up.

> Practically _every_ discussion I've _had_ with you, you've been wrong.

Practically every discussion I've had with you, you've been wrong.

> Further, you've _never_once_ admitted to being wrong.

Further, you simply cut off communication because it hurts your pride to
admit your mistakes.

When I make a mistake, I admit it.

---Dan