Quick Sort Analysis

Best Case

The best case for the quick sort occurs when each partition splits the array into two equal halves. Then, the overall cost for sorting $n$ items is given by:

Since the size of each half is $n/2$, this leads directly to the recurrence relation:

$$C(n) = 2 C(\frac{n}{2}) + n \quad ; \quad C(1) = 0$$

This is the same recurrence relation that governs the merge sort. We know that it results in a cost function that is $O(n \ln n)$.

Worst Case

The worst case for the quick sort occurs when the partition does not split the array (i.e., when one set has no elements at all). Ironically, this happens when the array is sorted!

In this situation, the cost of the sort can be resolved into:

Thus, the recurrence relation in this case is slightly different:

$$C(n) = C(n-1) + n \quad ; \quad C(1) = 0$$

Solving the recurrence relation is straight forward:

$$\begin{array}{rclc} C(n) &=& C(n-1) + n & \\\\ &=& C(n-2) + (n-1) + n &\\\\ &=& C(n-3) + (n-2) + (n-1) + n &\\\\ &=& \cdots\\\\ &=& C(1) + 2 + \cdots + (n-2) + (n-1) + n &\\\\ &=& \displaystyle{\frac{n(n+1)}{2} - 1} &\\\\ \end{array}$$

Thus, $C(n)$ is $O(n^2)$.

Average Case and Improvements

Since the worst cases occurs when the array is ordered (or highly ordered), we can give ourselves a probabilistic guarantee that this doesn't happen by purposefully shuffling the elements of the array before using the quick sort algorithm. This comes at a slight extra cost, but is worth it to minimize to the point of negligibility the possibility of a $O(n^2)$ cost.

While we won't derive it here, on average, the quick sort results in a number of comparisons $\sim 1.39 n \ln n$.

That means one has $39$ percent more comparisons than merge sort. However, quick sort is faster than merge sort in practice, because there is less data movement during the sort.

Amazingly, we can improve on the quick sort algorithm with a few modifications: