Overview of Quicksort

Like merge sort, quicksort uses divide-and-conquer, and so it's a recursive algorithm. The way that quicksort uses divide-and-conquer is a little different from how merge sort does. In merge sort, the divide step does hardly anything, and all the real work happens in the combine step. Quicksort is the opposite: all the real work happens in the divide step. In fact, the combine step in quicksort does absolutely nothing.

Quicksort has a couple of other differences from merge sort. Quicksort works in place. And its worst-case running time is as bad as selection sort's and insertion sort's: $\Theta(n2)$. But its average-case running time is as good as merge sort's: $\Theta(n \log n)$. So why think about quicksort when merge sort is at least as good? That's because the constant factor hidden in the big–$\Theta$ notation for quicksort is quite good. In practice, quicksort outperforms merge sort, and it significantly outperforms selection sort and insertion sort.

Here is how quicksort uses divide-and-conquer. As with merge sort, think of sorting a subarray $array[p \cdots r]$, where initially the subarray is $array[0 \cdots n-1$].

1. Divide by choosing any element in the subarray $array[p \cdots r]$. Call this element the pivot. Rearrange the elements in $array[p \cdots r]$ so that all other elements in $array[p\cdots r]$ ...