Emil (Emil@example.com) on 9/8/09 wrote:
---------------------------
>rwessel (robertwessel@yahoo.com) on 9/8/09 wrote:
>
>>*That's the exact bounds, BTW (the base two logarithm of N factorial). Unlike
>>the "order" that Big-Oh notation describes.
>
>I tried to find what the maximum theoretical sorting efficiency could be. Some
>places claim O(N log N) but don't reference how they get to this value.
>
>Do you have a better reference off hand?


Knuth's "The Art of Computer Programming, Volume 3, Sorting and Searching."

As I mentioned before, a general purpose sort *must* generate lg(n!) bits of information (note: "lg()" is specifically the base two logarithm). The proof of that is fairly simple. Informally: There are n! ways to rearrange the input records, it's the job of the sort to pick which of those n! possible rearrangements results in the correct order. Distinguishing between those n! possible rearrangements requires lg(n!) bits. For example, let’s say you had ten elements to sort. Those can be rearranged in 10!, or 3,628,800 ways. Uniquely identifying all of those 3.6 million combination requires a bit under 22 bits (21.791... to be more precise), as 2**21 can only represent about two million possibilities, and 2**22 can represent about four million. Thus a sort which can generate one bit of information with each step (the maximum possible for a lt/eq/gt comparison between two elements), you'll need to perform lg(n!) steps - or 22 steps in the case of 10 elements.

There are a number of comparison based sorts with performance of O(n*log(n)). Stirling's Approximation tells us that n*lg(n) is approximately a small (sort-of) constant factor more than lg(n!), thus O(n*log(n)) and O(lg(n!)) are basically the same, since Big-Oh basically ignores the constant factor (and which is why the base of the logarithm in meaningless within the scope of Big-Oh).

Now as far as theoretical efficiency goes, it depends on exactly what you mean by that. As I said, you *will* need to generate lg(n!) bits of information in the general case, but the number of steps you need to take is *not* necessarily related to that expression. As a simple case, consider Quicksort and Heapsort. Both are O(n*log(n)) sort, but the constant factor on Heap sort is typically about twice that of Quicksort, so Quicksort is often twice as fast as Heapsort.

If you stick with comparison based sorts, probably the strategy that produces the minimum number of comparisons is Merge Insertion, although it's only be proved to be optimal for a relatively small number of N's (3 to 12 and 20 and 21, IIRC). For other/larger values, it's probable or even provable that Merge Insertion performs more than lg(n!) comparisons (I don't remember the status of the proof, but IIRC, for 13 elements Merge Insertion generates 34 comparisons, but it's strongly suspected that it's possible to sort 13 elements with no more than 33 comparisons).

Of course it's far from clear that minimizing the number of comparisons is "optimum" in any particular case. Simple Binary Insertion generates O(n*log(n)) comparisons (more exactly: sum(x=2..n, ceil(lg(x))) – which is only slightly worse than Merge Insertion), but O(n**2) data *moves* (which is often horrible). Nor is Merge Insertion easy or particularly efficient to implement. That's where Quicksort wins - the inner loops are *very* short.

Anyway, there's no reason to constrain yourself to basic operations that generate only a single bit of data per step. For example, the distribution function of a Radix sort generates approximately lg(r) bits of information per step under optimal conditions, where r is the radix. For example, if you did an eight-way radix sort, you're generating approximately three (lg(8)) bits of information per step (put another way it's sorting three bits of the key at a time), and the Radix sort could run in as few as lg(n!)/3 steps. In fact, a Radix sort will sort in O(n*m), where m is the length of the key (rather obviously unrelated in terms of Big-Oh to n*log(n)).

Unfortunately most sorts that involve some sort of address computation (like Radix sort), tend to perform well only under selected circumstances. For example, radix sort performs well only if the key is short. Consider sorting a million records - a O(n*log(n)) Quicksort can run in about 20 million steps, regardless of the length of the key. An eight-way Radix sort will run in about 5 million steps if the key is 15 bits long (15/lg(8) = 5) or 100 million steps if the key is 300 bits long (300/lg(8) = 100). In practice the comparison based sorts perform best in the general case, because key lengths are almost always too long. But not always, of course - consider sorting by ZIP+4 code (the nine digit US Postal Code), which has a effective key length a bit under 30 bits. Assuming a eight-way radix sort, and ignoring the constant factor, Radix sort will be faster than an O(n*log(n)) sort with more than about 1024 records – and about twice as fast for one million records.

Nor does any of that put a lower limit on *time* to sort. Many sorts can be parallelized. For example, you can parallelize the partitioning operations of Quicksort, although your maximum possible speedup, using an infinite number of processors) is lg(n), so total wall-clock sort time can be O(n). While infinite numbers of CPUs is impractical a several fold speedup is plausible (although you're still doing the same amount of work, just parts in parallel).

Other parallel sorts can be much faster than that in terms of time. For example, Batcher's Merge-Exchange can sort in O(log(n)**2) *time*, but it does O(n*log(n)**2) *work*. So for our example million record sort, parallel Quicksort has a lower bound of one million time units (while still performing 20 million work units), but Batcher's can sort in 400 time units (but while doing *400* million work units). And remember those are Big-Oh, and there's a constant factor I'm ignoring.

But in practice the best practical single threaded general purpose sorts sort in O(n*log(n)), which *is* close to the theoretical limit (within a constant factor, anyway), assuming one-bit-per-operation.

But go read Knuth. And figure out what you mean by “maximum theoretical sorting efficiency.”