Path: utzoo!attcan!uunet!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: <25141:Nov1219:08:0490@kramden.acf.nyu.edu>
Date: 12 Nov 90 19:08:04 GMT
References: <16709:Nov1113:56:2390@kramden.acf.nyu.edu> <237@smds.UUCP> <2432@wn1.sci.kun.nl>
Organization: IR
Lines: 34

In article <2432@wn1.sci.kun.nl> hansm@cs.kun.nl (Hans Mulder) writes:
  [ Hans attributed to Richard, but I actually said: ]
> > .....  I'll continue to
> > sort n-byte files in time between bn and cn seconds for nonzero b and c.
  [ Hans paraphrased Richard, attributing it to me: ]
> if the file
> contains N records, they must be at least log(N) long, in order to be
> distinct,

There is no reason to assume distinctness. In fact, many real database
applications feature large numbers of identical keys. It would be silly
to use an O(n log n) sort when a constant-time-per-byte sort suffices.

However, you are correct that a linear sort is asymptotically no faster
than an O(n log n)-per-record sort *if* the records are distinct.

End technical content.

This whole discussion has me rather amused. I just received mail from a
know-it-all who, in a remarkable display of alliteration, wrote

  You're winning big bozo points with your blustering bad mathematics

(presumably in reference to this thread). Hey, bozo, I know you're
listening, and I challenge you to identify yourself and to point out any
example of ``blustering bad mathematics'' in any of my articles in this
group. I know you'll be too scared to come out of the closet, because
once you bother to shed your computer science training and actually
think, you'll realize that I'm right. Or will you just go ahead and
post, and give me the fun of flaming you for it? For several weeks now
I've been in the perfect mood to take out my anger on a stupid yuckie
who wouldn't know mathematical truth if it hit him in the face.

---Dan