Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!wuarchive!udel!cis.udel.edu
From: carroll@cis.udel.edu (Mark Carroll)
Newsgroups: comp.lang.misc
Subject: Re: Sorting bounds
Message-ID: <37256@nigel.ee.udel.edu>
Date: 26 Nov 90 19:16:45 GMT
References: <1990Nov20.202143.10746@craycos.com> <6327:Nov2022:30:2490@kramden.acf.nyu.edu>
Sender: usenet@ee.udel.edu
Organization: University of Delaware
Lines: 47
Nntp-Posting-Host: sol.cis.udel.edu

In article <6327:Nov2022:30:2490@kramden.acf.nyu.edu> brnstnd@kramden.acf.nyu.edu (Dan Bernstein) writes:
>In article <1990Nov20.202143.10746@craycos.com> jrbd@craycos.com (James Davies) writes:
>> Sorry to inject some mathematics into this lovely flamefest, but...
>> The bound on sorting is O(N log N) comparisons because you must be able to
>> generate all of the N! possible permutations of the N inputs.
>
>That bound is only valid if the only permitted operation is comparison.
>
>  [ on the supposed fact that radix sorting is n log n ]
>> This is most evident when you try to make your bucket sort scale up to 
>> arbitrary sizes (like, say, sorting a trainload of tapes...)
>
>The scale factor between sorting 100 of Ritchie's boxcars and just 1 of
>them is almost exactly 100---internal sorting by far dominates any
>merging. So for practical purposes (even in such a ridiculously large
>situation) sorting is linear in the number of bytes. And for theoretical
>purposes, since any immediately accessible byte of memory is accessible
>in constant time under any realistic computational model, sorting is
>also linear in the number of bytes.
>

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

Proof:
  Suppose I have a list of N keys that need to be sorted.
  Given some way of converting these keys to numbers in constant
  time, I've got a list of numbers that can be sorted linearly in
  the number of bytes required to store that list of numbers. 

  How many bytes is that, in terms of the number of keys? Well, the
  number of bits required to uniquely store a value between 1 and N 
  is O(log n), so the number of bytes required to store
  those N keys is O(n log n). The time to sort is linear in this, 
  so sorting time is O(n log n).

In other words, this entire argument has been zero content. Yes, n log n
IS the realistic lower bound on sorting N keys. Yes, N keys can be sorted
in time linear to the number of bytes. Both right, both mean EXACTLY the
same thing.

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

>---Dan