Analysis of back-and-forth version of quicksort

Consider back-and-forth quicksort (described in hwk-6, prob 3) applied to $n$ values. Let $T(n)$ be the average number of comparisons the algorithm uses. We know $T(0) = T(1) = 0$. The partition operation is done with exactly $n-1$ comparisons. Assume that the partition value turns out to have sorted rank (order position) $q$. Then we have its location, but we still have to recursively quicksort the $q-1$ smallest values and the $n-q$ largest values. So, for a fixed $q$, the remaining steps of quicksort take $T(q-1) + T(n-q)$ comparisons on average.

But the value of $q$ is equally likely to be any integer from $1$ to $n$. So, averaging over all possible values of $q$, the expected number of remaining steps of quicksort takes is $\sum_{q=1}^n \frac{1}{n} [T(q-1) + T(n-q)]$ comparisons.

We claim that $T(n) \le a n \ln n$ for some constant $a$ and $n \ge 1$. Proof by constructive induction.

Base case: $n=1$: $T(1) = 0$ and $a \cdot 1 \cdot \ln 1 = 0$.

Induction step: Assume it holds for all positive integers less than $n$. Then

$$\begin{eqnarray*} T(n) & = & \sum_{q=1}^n \frac{1}{n} [T(q-1) + T(n-q)] + n - 1 ... ... & \le & a n \ln n ~~~~~\mbox{{\bf if} the induction is to hold} \end{eqnarray*}$$

Some straightfoward algebra now shows that $a\geq 2$, so $a=2$ is the tightest upper bound we can get with this argument, and

$$T(n) \le 2n \ln n ~=~ 2 (\ln 2) n \lg n ~\approx~ 1.39 n \lg n$$

Web Accessibility