Quicksort
The divide-and-conquer sort that’s fast on average, fragile in the worst case, and still the default choice behind most general-purpose sort functions in use today.
- The core idea: partition, then conquer
- Choosing a pivot — the decision that makes or breaks performance
- In-place partitioning, step by step
- Code in C, Python, and Java
- Best, average, and worst-case complexity
- Why quicksort is usually faster than merge sort in practice
- Stability, recursion depth, and other gotchas
The core idea: partition, then conquer
Quicksort, devised by Tony Hoare in 1959, is built on a single idea repeated recursively: pick one element from the list — call it the pivot — and rearrange every other element around it, so that everything smaller than the pivot ends up to its left and everything larger ends up to its right. The pivot itself is now sitting in its final, correct position. Recursively apply the same process to the left chunk and the right chunk, and eventually every element settles into place.
This is the “divide and conquer” pattern in its purest form. Unlike merge sort, which splits a list in half regardless of its contents and does the real work while merging the pieces back together, quicksort does its real work during the split itself — the partitioning step — and the recursive calls afterward require comparatively little additional effort.
The dark bar is the pivot — everything shorter moves left of it, everything taller moves right.
Choosing a pivot — the decision that makes or breaks performance
Quicksort’s entire performance story comes down to one question: how good is the pivot? An ideal pivot splits the list into two roughly equal halves every time, producing excellent average-case behavior. A terrible pivot — always picking the smallest or largest remaining element — splits the list into one chunk of size zero and one of size n - 1, degrading the algorithm to something behaving like a much slower selection-sort pattern.
The naive choice — always picking the first or last element as the pivot — works fine on random data but is a known weak point: an already-sorted or reverse-sorted list can trigger worst-case behavior. Two common fixes address this. The first is choosing the pivot randomly, which makes worst-case behavior astronomically unlikely. The second is the “median of three” heuristic — looking at the first, middle, and last elements and picking whichever is the median of those three.
In-place partitioning: the C implementation
The most widely taught partitioning method, due to Nico Lomuto, walks through the sublist with two markers: one tracking the boundary between “confirmed smaller than pivot” and “not yet checked,” and another scanning forward element by element. Every time the scanning marker finds something smaller than the pivot, it swaps that element into the boundary zone and advances the boundary.
void swap(int* a, int* b) { int temp = *a; *a = *b; *b = temp; } int partition(int arr[], int low, int high) { int pivot = arr[high]; /* last element as pivot */ int boundary = low - 1; for (int i = low; i < high; i++) { if (arr[i] < pivot) { boundary++; swap(&arr[boundary], &arr[i]); } } swap(&arr[boundary + 1], &arr[high]); return boundary + 1; } void quicksort(int arr[], int low, int high) { if (low < high) { int pivotIndex = partition(arr, low, high); quicksort(arr, low, pivotIndex - 1); quicksort(arr, pivotIndex + 1, high); } }
Every comparison and swap above happens within the original array — no second array is ever allocated. For large datasets where memory bandwidth matters, sorting in place rather than copying into auxiliary storage can make a measurable difference in real-world speed.
A cleaner read in Python
Python’s list comprehensions make a non-in-place version of quicksort almost embarrassingly short to write — useful for understanding the algorithm’s logic, even though it sacrifices the in-place memory advantage.
def quicksort(items): if len(items) <= 1: return items pivot = items[len(items) // 2] smaller = [x for x in items if x < pivot] equal = [x for x in items if x == pivot] larger = [x for x in items if x > pivot] return quicksort(smaller) + equal + quicksort(larger)
Notice the middle element is used as the pivot — a small step toward median-of-three resistance, since the middle of an already-sorted or reverse-sorted list is a much safer choice than either end. This version also handles duplicate pivot values explicitly via the equal list, which avoids a subtle inefficiency that shows up if duplicates are routed entirely into one side of the partition.
Best, average, and worst-case complexity
| Case | Time complexity | When it happens |
|---|---|---|
| Best case | O(n log n) | Pivot consistently splits the list evenly |
| Average case | O(n log n) | Random or typical real-world data |
| Worst case | O(n²) | Pivot consistently picks the smallest or largest element |
The log n factor comes from the recursion depth in the well-balanced case: each level of recursion roughly halves the remaining work, so it takes about log₂ n levels to whittle the problem down to single elements. The worst case removes that balance entirely — if every partition splits off just one element, the recursion depth becomes n instead of log n, and the total work becomes quadratic.
Why quicksort is usually faster than merge sort in practice
Merge sort guarantees O(n log n) in every case — a real theoretical advantage over quicksort. And yet, in most general-purpose sorting libraries, a quicksort variant is still the default. The reason is almost entirely about constants that complexity notation hides: quicksort’s in-place partitioning has excellent cache locality, since it repeatedly works on contiguous, shrinking regions of the same array, while merge sort’s repeated allocation and merging into auxiliary arrays creates more memory traffic per element processed.
This is exactly why many production sorting routines — including the C standard library’s qsort and, historically, Java’s primitive-array sort — use quicksort or a closely related hybrid as their default, while reserving merge sort specifically for cases where stability is required.
Stability, recursion depth, and other gotchas
- Quicksort is not stable. Equal elements can end up reordered relative to each other; if stability matters, quicksort needs a tie-breaking modification or a different algorithm entirely.
- Recursion depth can spike on adversarial input. Without randomized or median-of-three pivot selection, a sorted or reverse-sorted input can drive recursion depth to
n, risking a stack overflow on very large inputs. - Tail-call optimization helps, but only partially. Recursing on the smaller partition first and looping on the larger one keeps worst-case stack depth to O(log n) — a standard production refinement worth knowing.
- Many real libraries use a hybrid. Switching to insertion sort once a sublist shrinks below some small threshold (often around 10–20 elements) avoids the overhead of recursive calls on data small enough that a simple algorithm is faster outright.