Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!zaphod.mps.ohio-state.edu!uakari.primate.wisc.edu!uflorida!haven!adm!cmcl2!kramden.acf.nyu.edu!brnstnd
From: brnstnd@kramden.acf.nyu.edu (Dan Bernstein)
Newsgroups: comp.lang.misc
Subject: Re: Sorting bounds
Message-ID: <20414:Nov2623:37:2390@kramden.acf.nyu.edu>
Date: 26 Nov 90 23:37:23 GMT
References: <1990Nov20.202143.10746@craycos.com> <6327:Nov2022:30:2490@kramden.acf.nyu.edu> <37256@nigel.ee.udel.edu>
Organization: IR
Lines: 52

Skip unless you have a dogmatic belief in n log n.

In article <37256@nigel.ee.udel.edu> carroll@cis.udel.edu (Mark Carroll) writes:
> Saying that sorting is "linear in the number of bytes" is truly foolish.
> It's nothing but a deceptive way of saying "Sorting takes time O(n lg n)
> in the number of keys".

Sorting *is* linear in the number of bytes. Sorting is *not* n log n in
the number of keys. The latter bound is only true under various
restrictions. It's not foolish to say an always true statement rather
than a sometimes false statement.

> Proof:
>   Suppose I have a list of N keys that need to be sorted.
  [ ... ]
> so the number of bytes required to store
>   those N keys is O(n log n).

That statement is false. That ``proof'' is not a proof.

Consider, for instance, N strings of total length L. I can sort them in
time O(L). L can be smaller than cN log N---the average length of the
strings might be constant, or asymptotically log log N, or whatever.
You claim that this is impossible. You're wrong.

> In other words, this entire argument has been zero content. Yes, n log n
> IS the realistic lower bound on sorting N keys.

No, it is not.

> Yes, N keys can be sorted
> in time linear to the number of bytes. Both right, both mean EXACTLY the
> same thing.

No, they do not. The linear bound is precise. The n log n bound is only
sometimes correct, and is much less precise.

> Incidentally, the best lower bound known, taking advantage of some of the
> special features of real machines to create a computation model that
> includes more than just strict comparisons is O(n log n / log log n). 

I was quite amused at this ``new'' result from a couple of years ago
(which, btw, I mentioned at the beginning of the sorting thread). If I
remember right, the method uses bit manipulations on integers, has a
huge constant of proportionality, and would only be used for real
problems by the criminally insane. Rather funny how computer science
advances backwards.

(Oh, and can you explain why your ``proof'' doesn't apply to this
method?)

---Dan