Quick Sort: Partitioning and Pivot Choice
Pick a pivot, partition the array so smaller values sit left and larger right, then sort each side by the same method.
Partitioning Is the Whole Algorithm
Quick sort chooses one value as the pivot and rearranges the array around it. One round:
- Choose pick one value as the pivot. Which one you pick decides whether the sort is O(n log n) or O(n²).
- Partition rearrange so everything smaller sits left of the pivot and everything larger sits right. One Θ(n) pass.
- Place the pivot is now in its final sorted position and never moves again.
- Recurse sort the left and right regions independently. No combine step: when both sides are sorted, the array is sorted.
That single fact is what makes the recursion work: after partitioning, the two sides are independent subproblems, and no value ever needs to cross the pivot.
The contrast with merge sort is exact and worth stating in those terms. Merge sort does trivial splitting and all its work in the combine step. Quick sort does all its work in the divide step and nothing at all in the combine — once both sides are sorted, the array is sorted, because partitioning already placed everything on the correct side.
- The pivot lands in its permanent position after one partition
- Values never cross the pivot afterwards, so the sides are independent
- One partition pass is Θ(n) comparisons
- No combine step — the work is entirely in the divide
Lomuto and Hoare
Lomuto partitioning takes the last element as pivot, keeps a boundary index i, and scans with j. Whenever a[j] <= pivot it advances the boundary and swaps. At the end it swaps the pivot into i+1. It is short and easy to prove correct, which is why it appears in most textbooks — but it performs more swaps, and it degrades badly on arrays with many duplicates.
Hoare partitioning runs two indices inward from both ends, stopping when the left index finds a value ≥ pivot and the right finds one ≤ pivot, then swapping the pair. It does roughly three times fewer swaps and handles duplicates far better. Its awkwardness is that it does not place the pivot at the returned index, so the recursive calls must be written as (lo, p) and (p+1, hi) rather than excluding the middle.
For arrays with many repeated keys, three-way partitioning (Dutch national flag) splits into < pivot, = pivot, and > pivot, then recurses only on the outer two. An array of all-equal keys then sorts in linear time instead of quadratic.
| Scheme | Swaps | Duplicates | Pivot placed? |
|---|---|---|---|
| Lomuto | More | Degrades to O(n²) | Yes, at returned index |
| Hoare | ≈ 3× fewer | Handles well | No — split point only |
| Three-way | Moderate | Linear on all-equal | Whole equal block |
- Lomuto is simpler to prove; Hoare is faster in practice
- Hoare's return value is a split point, not the pivot's index
- Three-way partitioning is the fix for many duplicate keys
- All three are Θ(n) for one partition pass
Sort with quick sort
def quick_sort(values, lo=0, hi=None):
if hi is None:
hi = len(values) - 1
if lo < hi:
p = partition(values, lo, hi)
quick_sort(values, lo, p - 1) # the pivot itself is excluded
quick_sort(values, p + 1, hi)
return values
def partition(values, lo, hi):
pivot = values[hi] # Lomuto: last element is the pivot
i = lo - 1 # boundary of the "smaller" region
for j in range(lo, hi):
if values[j] <= pivot:
i += 1
values[i], values[j] = values[j], values[i]
values[i + 1], values[hi] = values[hi], values[i + 1]
return i + 1 # the pivot's final index
print(quick_sort([7, 2, 9, 4, 5]))
#include <iostream>
#include <vector>
int partition(std::vector<int>& values, int lo, int hi) {
const int pivot = values[hi]; // Lomuto: last element is the pivot
int i = lo - 1; // boundary of the "smaller" region
for (int j = lo; j < hi; ++j) {
if (values[j] <= pivot) std::swap(values[++i], values[j]);
}
std::swap(values[i + 1], values[hi]);
return i + 1; // the pivot's final index
}
void quickSort(std::vector<int>& values, int lo, int hi) {
if (lo < hi) {
const int p = partition(values, lo, hi);
quickSort(values, lo, p - 1); // the pivot itself is excluded
quickSort(values, p + 1, hi);
}
}
int main() {
std::vector<int> values {
7, 2, 9, 4, 5
};
quickSort(values, 0, static_cast<int>(values.size()) - 1);
for (int v : values) std::cout << v << ' ';
std::cout << '\n';
}import java.util.Arrays;
public class QuickSort {
static int partition(int[] values, int lo, int hi) {
int pivot = values[hi]; // Lomuto: last element is the pivot
int i = lo - 1; // boundary of the "smaller" region
for (int j = lo; j < hi; j++) {
if (values[j] <= pivot) {
i++;
int tmp = values[i];
values[i] = values[j];
values[j] = tmp;
}
}
int tmp = values[i + 1];
values[i + 1] = values[hi];
values[hi] = tmp;
return i + 1; // the pivot's final index
}
static void quickSort(int[] values, int lo, int hi) {
if (lo < hi) {
int p = partition(values, lo, hi);
quickSort(values, lo, p - 1); // the pivot itself is excluded
quickSort(values, p + 1, hi);
}
}
public static void main(String[] args) {
int[] values = {7, 2, 9, 4, 5};
quickSort(values, 0, values.length - 1);
System.out.println(Arrays.toString(values));
}
}Step through it
Running on [7, 2, 9, 4, 5]
On paper: One Partition Pass
Take [3, 1, 4, 7, 5, 9, 8] and choose 5 as the pivot:
- Scan compare each of the other six values against the pivot 5. Six comparisons, one pass.
- Separate 3, 1 and 4 are smaller and belong left; 7, 9 and 8 are larger and belong right.
- Place the pivot the array becomes
[3, 1, 4, | 5 | 7, 9, 8]. Index 3 is where 5 belongs in the finished array. - Recurse sort
[3, 1, 4]and[7, 9, 8]independently. The pivot is excluded from both calls.
Two points earn marks in an exam. First, the left region is not sorted — it merely contains the right values, and sorting it is the next subproblem. Second, the pivot is excluded from further work, so each level handles strictly fewer than n elements.
- After partitioning, the pivot is final; the sides are merely separated
- Neither side is sorted yet — that is the recursive step
- The pivot is excluded from both recursive calls
- One pass is n−1 comparisons against the pivot
Why a Bad Pivot Costs O(n²)
If every partition splits the array roughly in half, the recursion has log n levels and Θ(n) work per level: O(n log n).
If instead each partition peels off a single element, the recursion has n levels with Θ(n) work each — O(n²), plus O(n) stack depth that can overflow.
The trap is that this worst case is not exotic. With a first-element or last-element pivot, already-sorted input triggers it exactly: every pivot is the minimum, every partition is empty on one side. Sorted data is the single most common shape of real input, so the naive implementation fails precisely where it should be fastest. This is the flaw merge sort does not have, and the reason its guarantee is sometimes worth the O(n) memory.
| Pivot strategy | Sorted input | Adversarial input |
|---|---|---|
| First or last element | O(n²) | O(n²) |
| Median of three | O(n log n) | O(n²), rare |
| Random pivot | O(n log n) expected | O(n log n) expected |
| Introsort (heap fallback) | O(n log n) | O(n log n) |
- Balanced splits give log n depth; peeling one element gives n
- First-element pivots fail on exactly the most common input
- Recurse into the smaller side first to bound stack at O(log n)
- Randomisation removes any fixed adversarial input
How Libraries Make It Safe
Production implementations do not use plain quick sort. Median-of-three picks the median of the first, middle and last elements, which makes sorted input a good case rather than the worst one and costs two comparisons per call.
Introsort — the C++ std::sort in every major standard library — goes further: it tracks recursion depth, and if it exceeds roughly 2·log₂ n it switches the remaining subarray to heap sort. That converts the O(n²) worst case into a hard O(n log n) guarantee while keeping quick sort's speed on ordinary input.
Finally, recursion stops early. Below about 16 elements the subarray is left unsorted, and a single insertion sort pass over the whole array finishes the job — cheap, because the array is nearly sorted by then. Quick sort remains the default for primitives because it is in-place and cache-friendly; where stability matters, libraries use a merge-based sort instead, since quick sort is not stable.
- Median-of-three turns sorted input into a good case
- Introsort falls back to heap sort past a depth limit
- Small subarrays are left for one final insertion sort pass
- Quick sort is not stable — use merge sort when order among equals matters