Median-of-3 partition
One way to improve the \(\textsc{Randomized-Quicksort}\) procedure is to partition around a pivot that is chosen more carefully than by picking a random element from the subarray. One common approach is the median-of-3 method: choose the pivot as the median (middle element) of a set of 3 elements randomly selected from the subarray. (See Exercise 7.4-6.) For this problem, let us assume that the elements in the input array \(A[1..n]\) are distinct and that \(n \geq 3\). We denote the sorted output array by \(A'[1..n]\). Using the median-of-3 method to choose the pivot element \(x\), define \(p_i = \Pr\{x = A'[i]\}\).
- Give an exact formula for \(p_i\) as a function of \(n\) and \(i\) for \(i = 2, 3, \ldots, n-1\). (Note that \(p_1 = p_n = 0\).)
- By what amount have we increased the likelihood of choosing the pivot as \(x = A'[\lfloor(n+1)/2\rfloor]\), the median of \(A[1..n]\), compared with the ordinary implementation? Assume that \(n \to \infty\), and give the limiting ratio of these probabilities.
- If we define a “good” split to mean choosing the pivot as \(x = A'[i]\), where \(n/3 \leq i \leq 2n/3\), by what amount have we increased the likelihood of getting a good split compared with the ordinary implementation? (Hint: Approximate the sum by an integral.)
- Argue that in the \(\Theta(n \lg n)\) running time of quicksort, the median-of-3 method affects only the constant factor.
The median-of-3 method improves pivot selection by choosing the middle value among three random elements, significantly increasing the probability of balanced partitions.
A.
We select 3 elements uniformly at random from the \(n\), which can be done in \(\binom{n}{3}\) ways. For \(A'[i]\) to be the median of the three, the set must consist of \(A'[i]\) itself, exactly one element smaller than it, and exactly one element larger than it. There are \(i-1\) elements smaller (positions \(1, \ldots, i-1\)) and \(n-i\) elements larger (positions \(i+1, \ldots, n\)), so the number of favorable choices is:
\[(i-1) \cdot 1 \cdot (n-i) = (i-1)(n-i)\]Therefore:
\[p_i = \frac{(i-1)(n-i)}{\binom{n}{3}} = \frac{6(i-1)(n-i)}{n(n-1)(n-2)}\]For \(i = 1\) or \(i = n\), we get \(p_1 = p_n = 0\) as expected (the minimum and maximum can never be medians of three elements).
B.
The median of the array is at position \(m = \lfloor (n+1)/2 \rfloor\). For large \(n\), \(m \approx n/2\).
With median-of-3:
\[p_{n/2} = \frac{6(n/2 - 1)(n - n/2)}{n(n-1)(n-2)} \approx \frac{6 \cdot (n/2) \cdot (n/2)}{n \cdot n \cdot n} = \frac{6n^2/4}{n^3} = \frac{3}{2n}\]With ordinary random pivot:
\[p_{\text{ordinary}} = \frac{1}{n}\]The ratio as \(n \to \infty\):
\[\lim_{n \to \infty} \frac{p_{n/2}}{p_{\text{ordinary}}} = \lim_{n \to \infty} \frac{3/(2n)}{1/n} = \frac{3}{2}\]We increase the probability of choosing the median by a factor of 3/2 or 50%.
C.
A good split has the pivot in the middle third: \(n/3 \leq i \leq 2n/3\).
With median-of-3:
\[\begin{align*} P_{\text{good, med3}} &= \sum_{i=n/3}^{2n/3} p_i = \sum_{i=n/3}^{2n/3} \frac{6(i-1)(n-i)}{n(n-1)(n-2)} \end{align*}\]Approximating with an integral (treating \(i\) as continuous):
\[\begin{align*} P_{\text{good, med3}} &\approx \frac{6}{n^3} \int_{n/3}^{2n/3} i(n-i) \, di \\ &= \frac{6}{n^3} \int_{n/3}^{2n/3} (ni - i^2) \, di \\ &= \frac{6}{n^3} \left[\frac{ni^2}{2} - \frac{i^3}{3}\right]_{n/3}^{2n/3} \end{align*}\]Evaluating at the bounds:
At \(i = 2n/3\): \(\frac{n(2n/3)^2}{2} - \frac{(2n/3)^3}{3} = \frac{2n^3}{9} - \frac{8n^3}{81} = \frac{18n^3 - 8n^3}{81} = \frac{10n^3}{81}\)
At \(i = n/3\): \(\frac{n(n/3)^2}{2} - \frac{(n/3)^3}{3} = \frac{n^3}{18} - \frac{n^3}{81} = \frac{9n^3 - 2n^3}{162} = \frac{7n^3}{162}\)
Difference: \(\frac{10n^3}{81} - \frac{7n^3}{162} = \frac{20n^3 - 7n^3}{162} = \frac{13n^3}{162}\)
Thus:
\[P_{\text{good, med3}} \approx \frac{6}{n^3} \cdot \frac{13n^3}{162} = \frac{78}{162} = \frac{13}{27} \approx 0.481\]With ordinary random pivot:
\[P_{\text{good, ord}} = \frac{2n/3 - n/3}{n} = \frac{n/3}{n} = \frac{1}{3} \approx 0.333\]The ratio:
\[\frac{P_{\text{good, med3}}}{P_{\text{good, ord}}} = \frac{13/27}{1/3} = \frac{13}{9} \approx 1.44\]We increase the probability of a good split by approximately 44%.
D.
The median-of-3 method affects only constant factors, not the asymptotic running time. The expected running time of quicksort is \(\Theta(n \lg n)\) as long as we achieve reasonably balanced splits with constant probability, and both methods satisfy this:
- Ordinary: 50% probability of better than 1/4-to-3/4 split
- Median-of-3: Higher probability of balanced splits
Both lead to \(O(\lg n)\) expected depth, and \(O(n)\) work per level, giving \(O(n \lg n)\) total.
The median-of-3 method improves the constant factor (fewer comparisons in practice) but doesn’t change the \(\Theta(n \lg n)\) asymptotic bound.