Sorting algorithms - Data Structures and Problem Solving Using Java - page 383

We may assume only the given—namely, that, because the items need to be
sorted, any two items can be compared.
Next, we prove one of the most fundamental theorems in computer sci-
ence, as Theorem 8.3. Recall first that the product of the first N positive inte-
gers is N !. The proof is an existence proof, which is somewhat abstract. It
shows that some bad input must always exist.

Theorem 8.3

Any algorithm that sorts by using element comparisons only must use at least
⎡ ⎤

comparisons for some input sequence.

log ( N !)

Proof

We may regard the possible inputs as any of the permutations of 1, 2, , N because
only the relative order of the input items matters, not their actual values. Thus the num-
ber of possible inputs is the number of different arrangements of N items, which is
exactly N ! . Let be the number of permutations that are consistent with the results
after the algorithm has processed i comparisons. Let F be the number of comparisons
processed when the sort terminates. We know the following: (a) because all
permutations are possible before the first comparison; (b) because, if more
than one permutation were possible, the algorithm could not terminate with confidence
that it produced the correct output; (c) there exists a permutation such that
because, after a comparison, each permutation goes into one of two
groups: the still-possible group and the no-longer-possible group. The larger of these
two groups must have at least half the permutations. Furthermore, there is at least one
permutation for which we can apply this logic throughout the comparison sequence.
The action of a sorting algorithm is thus to go from the state , in which all N ! permu-
tations are possible, to the final state , in which only one permutation is possible,
with the restriction that there exists an input such that in each comparison only half of
the permutations can be eliminated. By the halving principle, we know that at least
⎡

…

P i

P 0 = N !

P F = 1

P i P i ≥ ⁄ 2

- 1

P 0

P F

⎤ log ( N !) comparisons are required for that input.

How large is ⎡ log ( N !) ⎤ ? It is approximately N log N - 1.44 N .

summary

For most general internal sorting applications, an insertion sort, Shellsort,
mergesort, or quicksort is the method of choice. The decision regarding which
to use depends on the size of the input and on the underlying environment.
Insertion sort is appropriate for very small amounts of input. Shellsort is a
good choice for sorting moderate amounts of input. With a proper increment
sequence, it gives excellent performance and uses only a few lines of code.
Mergesort has O ( N log N ) worst-case performance but requires additional