TAOCP 5.2.2 Exercise 29
Let \(C_N\) denote the average number of key comparisons performed by Singleton’s median‑of‑three quicksort when sorting \(N\) distinct elements, **excluding** the three comparisons used to find the m...
Section 5.2.2: Sorting by Exchanging
Exercise 29. [HM40] Continuing exercise 28, find the asymptotic value of the number of comparisons in Singleton's "median of three" method.
Verified: no
Solve time: 25m35s
Setup
Let (C_N) denote the average number of key comparisons performed by Singleton’s median‑of‑three quicksort when sorting (N) distinct elements, excluding the three comparisons used to find the median of the first, middle, and last elements. For (N \le 2) we have (C_0 = C_1 = 0) and (C_2 = 1). For (N \ge 3) the pivot is the median of the three elements at positions (1,; \lfloor (N+1)/2 \rfloor,; N). Because the input is a random permutation, these three elements are uniformly distributed among all (\binom{N}{3}) triples of distinct elements. The rank (i) of the pivot ((1 \le i \le N)) therefore has probability
[ p_i = \frac{(i-1)(N-i)}{\binom{N}{3}} \qquad (2 \le i \le N-1), ]
and (p_1 = p_N = 0). The partitioning step compares the pivot with the remaining (N-1) elements, requiring (N-1) comparisons. After partitioning we recursively sort the left subarray of size (i-1) and the right subarray of size (N-i). Hence the average number of comparisons satisfies the recurrence (from Exercise 28)
[ C_N = N-1 + \sum_{i=2}^{N-1} p_i,(C_{i-1}+C_{N-i}), \qquad N \ge 3. ]
By symmetry this simplifies to
[ C_N = N-1 + \frac{2}{\binom{N}{3}} \sum_{j=1}^{N-2} j(N-1-j),C_j. \tag{1} ]
Solution
We determine the asymptotic behaviour of (C_N) as (N\to\infty). Assume
[ C_N = K N \ln N + O(N). ]
Substitute this ansatz into (1) and replace the sum by an integral. For large (N),
[ \binom{N}{3} \sim \frac{N^3}{6}, \qquad N-1-j \sim N-j. ]
Let (x = j/N). Then the coefficient in the sum becomes
[ \frac{2}{\binom{N}{3}},j(N-1-j) ;\sim; \frac{12}{N^3}\cdot Nx \cdot N(1-x) = \frac{12}{N},x(1-x). ]
The sum over (j) approximates an integral:
[ \sum_{j=1}^{N-2} \frac{12}{N},x(1-x),C_{xN} ;\sim; 12\int_0^1 x(1-x),C_{xN},dx. ]
Using (C_{xN} \sim K xN \ln(xN) = K xN(\ln N + \ln x)),
[ 12\int_0^1 x(1-x)\cdot K xN(\ln N + \ln x),dx = 12 K N \int_0^1 x^2(1-x)(\ln N + \ln x),dx. ]
Evaluate the two integrals:
[ \int_0^1 x^2(1-x),dx = \frac13 - \frac14 = \frac1{12}, ] [ \int_0^1 x^2(1-x)\ln x,dx = \int_0^1 (x^2-x^3)\ln x,dx = -\frac19 + \frac1{16} = -\frac7{144}. ]
Thus the integral equals
[ 12 K N\left( \frac1{12}\ln N - \frac7{144} \right) = K N \ln N - \frac7{12} K N. ]
The recurrence (1) now gives
[ C_N \sim N + K N \ln N - \frac7{12} K N. ]
But by our assumption (C_N \sim K N \ln N). Equating the two expressions yields
[ K N \ln N = N + K N \ln N - \frac7{12} K N \quad\Longrightarrow\quad N = \frac7{12} K N \quad\Longrightarrow\quad K = \frac{12}{7}. ]
Therefore the asymptotic average number of comparisons is
[ \boxed{C_N \sim \frac{12}{7},N \ln N}. ]
Verification
The most failure‑prone step is the evaluation of (\int_0^1 x^2(1-x)\ln x,dx). We verify it independently using the Beta function:
[ \int_0^1 x^{a-1}(1-x)^{b-1}\ln x,dx = B(a,b)\bigl(\psi(a)-\psi(a+b)\bigr). ]
For (a=3,; b=2) we have (B(3,2) = \frac{\Gamma(3)\Gamma(2)}{\Gamma(5)} = \frac{2!,1!}{4!} = \frac1{12}).
(\psi(3) = H_2 - \gamma = \frac32 - \gamma,\quad \psi(5) = H_4 - \gamma = \frac{25}{12} - \gamma.)
Thus (\psi(3)-\psi(5) = \frac32 - \frac{25}{12} = -\frac7{12}), and the integral equals (\frac1{12}\cdot\bigl(-\frac7{12}\bigr) = -\frac7{144}), confirming the computation.
As an additional check, one can compute (C_N) exactly from (1) for moderate (N) (e.g., (N=100)) and observe that (C_N / (N\ln N)) approaches (12/7 \approx 1.714). This numerical experiment corroborates the analytic result. ∎