Quicksort sorts a list by selecting a pivot, partitioning the other elements around it, and recursively sorting the resulting smaller sections. The recursion stops when a section contains zero or one element because that section is already sorted.
The recursive mechanism
Each recursive call performs three main steps:
- Choose a pivot from the current section of the list. Depending on the implementation, this could be the first, last, middle, or a randomly selected element.
- Partition the section so that values smaller than the pivot appear before it and values greater than the pivot appear after it. The pivot is then in its final sorted position.
- Recursively apply quicksort to the left and right partitions.
The base case is essential: if the current section has fewer than two elements, return without making another recursive call.
QUICKSORT(list)
if length(list) <= 1
return list
pivot = choosePivot(list)
lower = values less than pivot
equal = values equal to pivot
higher = values greater than pivot
return QUICKSORT(lower) + equal + QUICKSORT(higher)
For example, consider [7, 2, 9, 4, 3] with pivot 4. Partitioning produces [2, 3], [4], and [7, 9]. Quicksort recursively sorts [2, 3] and [7, 9], then combines the results to produce [2, 3, 4, 7, 9].
| Case | Performance |
|---|---|
| Balanced partitions | Average time complexity of and average recursion depth of |
| Highly unbalanced partitions | Worst-case time complexity of and recursion depth of |
A common misconception is that recursion itself sorts the values. In fact, partitioning moves values into the correct regions; recursion repeatedly applies that process to smaller subproblems.
IB exam technique
For an HL trace question, show the pivot, both partitions, every recursive call, and the base cases. For an explanation question, connect the divide-and-conquer structure to the average and worst-case complexities, and state that pivot choice affects partition balance.
