Return to Revisions

It takes $3$ comparisons to determine the median of the three elements. However, we can set the pointers to the second and second-last element and thus save two comparisons. So, we need $n+2$ comparisons before we execute quicksort on the two new arrays. Since we can assume that the three elements for the median are picked randomly, there are $k(n-k-1)$ scenarios that lead to a left array of size $k$ and a right array of size $n-k-1$. Each scenario is equally likely, thus, we have to divide by \begin{align} \sum_{k=1}^{n-2}k(n-k-1)=\frac{n(n-1)(n-2)}{6} \end{align} The final recurrence relation describing the number of comparisons is \begin{align} C_n=&n+2+\frac{6}{n(n-1)(n-2)}\sum_{k=1}^{n-2}k(n-k-1)(C_k+C_{n-k-1})\\ =&n+2+\frac{12}{n(n-1)(n-2)}\sum_{k=1}^{n-2}k(n-k-1)C_k \end{align} The recurrence can be simplified to \begin{align} (n+1)(n+2)C_{n+2}-2(n-1)(n+1)C_{n+1}+(n + 2) (n - 5)C_n=&6 (2 n + 3) \end{align} Wolfram Alpha gives the solution \begin{align} C(n) = \frac{1}{49} (7 c_1 (n + 1) + \frac{35280 c_2}{(n - 5) (n - 4) (n - 3) (n - 2) (n - 1) n} + 84 (n + 1) H_n - 54 n - 19) \end{align}