Path: utzoo!censor!geac!torsqnt!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: Lying
Message-ID: <15802:Nov1605:26:3790@kramden.acf.nyu.edu>
Date: 16 Nov 90 05:26:37 GMT
References: <6097@lanl.gov>
Organization: IR
Lines: 68

The saga continues: Jim finally finds a reference for Dan's supposed
statement that sorting is linear time (though it was in mail, not news).
But he fails to notice the word ``numbers''! Fans, keep the word
``numbers'' in your head. Remember ``numbers.'' Remember that machine
addresses are fixed length (typically length 4). Remember that sorting
numbers is not the same as sorting in general. Dan points out Jim's
mistake in excruciating detail and flames Jim for it. Life goes on.

In article <6097@lanl.gov> jlg@lanl.gov (Jim Giles) writes:
> A certain other contributor to this newsgroup claims to have _never_
> asserted that sorting could be done in linear time _without_ mentioning
> it was linear in the number of bytes and not the number of keys.

Not in news, anyway. But I'll accept your supposed example, then flame
you to death for your mistake.

>   > (Actually, you might speed the _test_ up by sorting the addresses of all
>   > potentially aliased objects and then moving through the sorted list and
>   > comparing adjacent items.  This is still _at_least_ N*log(N).
>   Great, now you don't even know how to sort a collection of numbers in
>   linear time.

Notice, everybody, the word ``numbers'' there. ``Sort a collection of
numbers.'' Notice that both Jim and I are talking about machine
addresses, which are numbers typically of length 2 or 4 bytes.

> This was a direct quote from an email message dated 23 Jul, 1990.

Correct.

> I took that as implicit permission to
> quote private mail communications over the net.

No problem. Fair use is rarely a problem in quoting short sections of
e-mail. Libel is.

> As usual, I don't expect _any_ apology (or indeed, any response at all)
> from the other party to this travesty.

I will not apologize, because you have not demonstrated me wrong.
Please, somebody with some intelligence, confirm that the word
``numbers'' does indeed appear in the above description? That I was
talking about sorting numbers, not about sorting in general? That my
statement is correct, and that sorting (fixed-length, as in machine)
numbers is, indeed, a linear problem?

Somebody who's been paying attention to this discussion, please confirm
that Jim has accused me of saying that sorting is linear time? Please
express an opinion on whether the above quote---which has to do with
sorting a collection of numbers, specifically machine addresses---is or
is not applicable to Jim's accusation that I have said sorting is linear
time.

Jim, I expect an apology from you. What you have just done in this
discussion is an example of what I mean by perversion. You take an issue
(whether my statements about sorting have or have not been correct). You
then change the issue into something else. By failing to quote enough of
previous articles, you introduce enough discontinuity that some readers
don't notice your perversion. And you continue to pervert what was said,
in order to cover your wounded ass.

I have not said that sorting is linear without qualification. I believe
that in news I have not said that sorting is linear without adding the
specific phrase ``in the number of bytes,'' though I am not so sure
about this. I am sure that my perceptions of radix sorting are correct.
I see no explanation for Jim's article but intentional perversion.

---Dan