Comparisons using Quicksort with the median as the pivot

Question

Background

Using a simplified Quicksort algorithm where the first element of the array is assigned as the pivot we get the following pseudocode for the algorithm:

Quicksort($a$):

• (1) If length($a$) $> 1$, then

• 1.1) pivot $← a [1]$.
• 1.2) less $← a[a <$ pivot].
• 1.3) equals $← a[a ==$ pivot].
• 1.4) greater $← a[a >$ pivot].
• 1.5) $a ←$ concat(Quicksort(less), equals, Quicksort(greater)).

• (2) Output $a$.

It is clear to see that the total number of comparisons will follow the recurrence equation:

$$C(n) = C(n-1) + (n-1) \space \space \text{ where } \space C(2) = 1$$

From here we see that $C(n) = \Theta (n^2)$

Here is the context under which this came up:

Question

The above is clear to me, however, I have now read that if we use the median as a pivot (which can be identified in $\Theta (n)$ time), then we get the following recurrence inequality:

$$ C(n) \leq 2C ( \lceil n/2 \rceil -1) + Mn $$

And this gives the result that $C(n) = \Theta (n \log n)$.

---

How have these two results been derived (the recurrence inequality and time complexity for the updated algorithm)? The only difference is that we are computing the median each time. This is achieved in $\Theta (n)$ time each time that it is calculated but it still isn't entirely clear where this inequality comes from or why the new time complexity is $\Theta(n \log n)$ for the entire algorithm.

---

Here is the exact context under which it came up:

Answer 1

The genuine Quicksort is an in-place algorithm, and your version with concatenations uses extra memory and is much less efficient for this reason [$\Theta(n^2)$ instead of $O(n^2)$ with best case $O(n\log n)$]. Also, it is a waste of time to apply the trichotomy <, =, >, which costs two comparisons where you can do with a single.

This said, the behavior of Quicksort relies on the "balancing" of the pivot: it every pivot generates a partition with a single element on a side and the rest on the other side, the total complexity is indeed proportional to $n+(n-1)+(n-2)+\cdots $, which is $\Theta(n^2)$.

But if every pivot splits the array in two equal halves, the total complexity is like $n+\dfrac n2+\dfrac n2+\dfrac n4+\dfrac n4+\dfrac n4+\dfrac n4+\cdots$, which equals $n\log_2n$.

---

Note that Quicksort is never implemented with the median taken as the pivot, because the linear-time median algorithm is complicated and much slower than the partitioning process itself. If one needs an algorithm with guaranteed worst-case complexity $O(n\log n)$, Heapsort is a better choice.