Path: utzoo!utgpu!news-server.csri.toronto.edu!cs.utexas.edu!usc!zaphod.mps.ohio-state.edu!uakari.primate.wisc.edu!pikes!aspen.craycos.com!jrbd
From: jrbd@craycos.com (James Davies)
Newsgroups: comp.lang.misc
Subject: Sorting bounds
Message-ID: <1990Nov20.202143.10746@craycos.com>
Date: 20 Nov 90 20:21:43 GMT
Organization: Cray Computer Corporation
Lines: 21

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.  If each
comparison reduces the size of the remaining search space by a factor of
K, you must make log (N!) comparisons to choose the right permutation.
                    K

N! grows approximately as N**N (Stirling's approximation, I believe it's
called).  Therefore, log N! grows as N log N.  
(log(N**N) = log(N*N*N*..*N) = log(N) + log(N) +...+ log(N) = N * log(N))

Radix or bucket sorts may appear to be linear, but in fact they are also
N log N in comparisons.   (Picking one of K buckets requires a K-way 
comparison.)  The log term may be hidden in the addressing hardware of 
your memory, and may be hidden further by parallelism, but it's there.  
This is most evident when you try to make your bucket sort scale up to 
arbitrary sizes (like, say, sorting a trainload of tapes...)

						Jim Davies
						jrbd@craycos.com