Median-of-3 partition

One way to improve the RANDOMIZED-QUICKSORT procedure is to partition around a pivot that is chosen more carefully than by picking a random element from the sub array. 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 sub array. For this problem, let us assume that the elements in the input array A[1 ? n] are distinct and that n ≥ 3. We denote the sorted output array by A"[1 ? n]. Using the median-of-3 method to choose the pivot element x, define pi = Pr{x = A"[i]}.

a. Give an exact formula for pi as a function of n and i for i = 2, 3,..., n - 1. (Note that p1 = pn = 0.)

b. By what amount have we increased the likelihood of choosing the pivot as x = A"[⌊(n + 1/2⌋], the median of A[1 ? n], compared to the ordinary implementation? Assume that n → ∞, and give the limiting ratio of these probabilities.

c. If we define a "good" split to mean choosing the pivot as x = A"[i], where n/ ≤ i ≤ 2n/3, by what amount have we increased the likelihood of getting a good split compared to the ordinary implementation? (Hint: Approximate the sum by an integral.)

d. Argue that in the Ω(n lg n) running time of quicksort, the median-of-3 method affectsonly the constant factor.