Sorting n keys by binary comparisons needs O(n log n) steps on average; can a sort be faster than O(n log...

The basic theorem of sorting says that the average can be no better
than O(n log n).  However the theorem is a little misleading since O(n)
sorts exist for rather general classes of cases.  The basis for the
theorem is that a sort must distinguish between the n! possible
permutations.  It happens that n! is O(n**n).  The number of binary
comparisons required to distinguish the n! cases is O(log2 n!) which is
O(n log n).  This is the best possible average case.

The reason that the basic theorem is misleading is that is stated in
terms of binary comparisons.  This involves two assumptions.  The first
is that the binary comparison is the appropriate element of
measurement.  The second is that the only information to be used is
relative ordering information.

The problem with the first assumption is that the appropriate
fundamental operation is the machine operation.  All modern computers
are inherently doing parallel processing because they operate on all of
the bits of a word.  The second assumption is appropriate for the most
general class of sort where keys can be completely arbitrary; in
practice, however, additional information always exists and can be
exploited.

A good example of an O(n) sort is the generalized math sort.  Given n
keys, assign n buckets.  Make a first pass over the data to get the
smallest and largest element.  Make a second pass over the data and use
linear interpolation on the keys to get the bucket index.  After the
second pass use any sort method which is O(n) for almost sorted data.
In practice this sort is O(n); the provisos are beyond the scope of
this article.

Address space is important.  It can be shown (See Knuth) that if
auxilliary storage devices are needed then sorting must be O(n log n)
and that (I believe) that there is nothing better than a merge sort.

Finally, radix sorting is O(n log n), at best.  The reason is that the
keys must be at least log n bits long to represent n distinct keys.

-- Richard Harter, SMDS Inc. <g-rh@cca-unix>

This is a follow up to the sorting question.  To make things simple
suppose that we have N=2**n keys having the values 0 to N-1.  We wish
to create an array of N pointers to the N records which is sorted.
Assume that the array is being built in virtual memory in a standard
timesharing system.  The obvious way to do this is make one pass
through the data, looking at the keys, and filling in the pointers in
the array.  Surprisingly enough, this obvious algorithm can be highly
inefficient.  This happens when the size of the array is being built is
larger than the number of resident pages allocated to the sort process.
The reason is that a high percentage of page faults are generated.
(One of Knuth's problems is about this issue.)  Here is an analysis:

Consider a sort algorithm.  The usual scheme is to use some number of
bins, say B=2**b.  The data is sorted in a number of passes.  In each
pass each key is examined once; the corresponding record (or pointer)
is placed in one of the bins.  This placement will generate a page
fault whenever a page used by a bin is filled up and the process no
longer has any free resident pages.  Let A=2**a be the number of
resident pages and M=2**m be the number of records per page.  (I'm
making everything powers of two to make things simple.)  The total
number of pages that must be used during the pass is N/M.  A page fault
will be generated for each page.  (Initial filling up may be ignored.)
This cost is unavoidable.  Placement in bins may be followed by a merge
process, depending on the particular algorithm chosen.  The number of
passes will be (for an efficient sort) logB(N).  Thus the total number
of page faults will be:

                (N/M)*logB(N) = (N/M)*(n/b)

Call the quantity above the bin filling cost.  It is evident that this
cost is cut by increasing the number of bins.  If, however, the number
of bins is greater than the number of resident pages an additional cost
is incurred because there is the chance that a needed bin will not be
present when we want to put a record in it.  If the keys are
distributed randomly this will happen with probability (B-A)/B.  This
cost is incurred with each record.  Call this cost the bin retrieval
cost.  The cost per pass is N*(B-A)/B.  The number of bin retrieval
page faults is:

                N*((B-A)/B)*(n/b) ~= N*n/b

It is clear that the best choice for B is B=A if the bin retrieval cost
is to be avoided.  In that case the number of pages faults is
(N/M)*(n/a).  If B>A the total number of page faults is:

                N*n*[1/M + 1 -1/2**(b-a)]/b ~= N*n/b

The latter expression is smaller when 1/b < 1/(M*a), that is when b>Ma.
However, we must have b<n, which implies N>2**(Ma).  The simple "put
everything in the right place" algorithm of the first paragraph is
equivalent to setting B = N/M.  It is superior to a binary comparison
sort if either of these two cases hold:

        I        N < MA
        II        N > M * 2**(Ma)

In practice the latter case can only occur if the records being sorted
are large and the available resident memory is small.  If, for example,
there is only one page available and a record fills one page direct
placement is clearly superior.  In all other cases the required value
for N is enormous.

The conclusion is that the optimal sorting method (in terms of page
faults) is direct placement when ***all*** of the sorted data fits in
resident unpaged memory.  If this is not the case, the best sort uses a
separate bin for each available page.  (But you lose big if you
overestimate the number of available pages.)

Note 1:        There are some glosses in this analysis.  However the final
conclusion is correct.  There are limits to how much work I want to
do.

Note 2: In an earlier note I claimed that a math sort (i.e. estimated
direct placement) is O(N).  Unfortunately the page fault cost is also
O(N) for all but small N.  More on this anon.

-- Richard Harter, SMDS Inc.