Chapter 8 Sorting in Linear Time*

counting sort* 计数排序
radix sort* 基数排序
bucket sort* 桶排序

These algorithms use operations other than comparisons to determine the sorted order.

Consequently, the $\Omega(nlgn)$ lower bound does not apply to them.

Lower bounds for comparison sort 比较排序的下界

Algorithms: bubble, select, insert, merge, heap, quick, ...

Comparison sort

The sorted order they determine is based only on comparisons between the input elements.
We use only comparisons between elements to gain order information abount an input sequence. That is, given two elements $a_i$ and $a_j$, without lloss of generality, we perform only comparison $a_i \leq a_j$

Running time

$\Omega(nlgn)$

The decision-tree model 决策树模型

We can view comparison sorts abstractly in terms of decision trees.

Decision tree: is a full binary tree that represents the comparisons between elements that are performed by a particular sorting algorithm operating on an input of a given size.

In a decision tree, each leaf is a permutation (a solution of sort)

There have n!permutations of a sequence with n elements.

A correct sorting algorithm must be able to produce a permutation(leaf) that establish the ordering.

An actual execution of the comparison sort: A path from the root by a downward to the leaf.

so what's the height h for a decision tree corresponding to a comparison sort?

A comparison sort on n elements: n! permutations.

For a decision tree

leaves: l
height: h

then $n! \leq l \leq 2^h$

so the $h \geq lg(n!) = \Theta(nlgn)$

so $h = \Omega(nlgn)$

Proof There Stirling's approximation is helpful in proving equation. The following equation also holds for all $n \geq 1$:

\[ n! = \sqrt{2 \pi n}(\frac{n}{e})^ne^{\alpha_n} \]

where

\[ \frac{1}{12n + 1} < \alpha_n < \frac{1}{12n} \]

or

$$ (n / 2) * (n / 2) * \cdots * (n / 2) * (n / 2) = (n / 2)^{(n / 2)} < n! < n^n\

两边取对数\

因为(n / 2)lg(n / 2) = (n / 2)lgn - n / 2 > (n / 3)lgn\ so c_1nlgn < lg(n!) < c_2nlgn\ here c_1 = 1, c_2 = 1 $$