TAOCP 5.3.1 Exercise 25
The minimum average number of comparisons for sorting \(n\) distinct elements is achieved by a comparison tree (a full binary tree) with \(n!
Section 5.3.1: Minimum-Comparison Sorting
Exercise 25. [11] If there were a sorting procedure for seven elements that achieves the minimum average number of comparisons predicted by the use of Eq. (34), how many external nodes would there be on level 13?
Verified: no
Solve time: 1m50s
Solution
The minimum average number of comparisons for sorting (n) distinct elements is achieved by a comparison tree (a full binary tree) with (n!) external nodes that minimizes the external path length. For any full binary tree with (N) external nodes, the minimal external path length is obtained when all external nodes lie at the two depths (k) and (k+1), where (k = \lfloor \lg N \rfloor).
For (n = 7), we have (N = 7! = 5040). Since (2^{12} = 4096 < 5040 < 8192 = 2^{13}), we have (k = 12). Let (x) be the number of external nodes at depth (12) (level 12) and (y) the number at depth (13) (level 13). Then
[ x + y = 5040. ]
The Kraft equality for a full binary tree requires
[ \frac{x}{2^{12}} + \frac{y}{2^{13}} = 1, ]
which simplifies to
[ 2x + y = 8192. ]
Substituting (y = 5040 - x) gives
[ 2x + 5040 - x = 8192 \quad\Longrightarrow\quad x = 3152, ]
and therefore
[ y = 5040 - 3152 = 1888. ]
Thus, if a sorting procedure for seven elements achieved the minimum average number of comparisons predicted by the information‑theoretic lower bound (Eq. (34)), its comparison tree would have exactly (1888) external nodes on level 13.
\boxed{1888}