Quicksort and Partitioning
Imagine sorting ten million log lines by timestamp, in place. There is no extra memory to spare. No library call is available. You need an algorithm that rearranges the data itself. It should not copy data into new arrays at every step. Quicksort is the classical answer. It is a divide-and-conquer sorting algorithm. It sorts an array by rearranging it around a chosen element, called the pivot. Everything smaller ends up on one side. Everything larger ends up on the other. Quicksort matters because it is fast in practice. It uses almost no extra memory. Its inner loop is simple enough that real implementations squeeze enormous performance out of it. These implementations range from C's `qsort` to Java's dual-pivot array sort. They also include database engines sorting intermediate results. Unlike Merge Sort, which guarantees Θ(n log n) time but needs Θ(n) auxiliary space, quicksort sorts in place. It moves elements within the original array. It uses only a constant amount of extra bookkeeping. The central mechanism is partitioning. Given a chosen pivot value, rearrange the subarray. Elements less than the pivot come before it. Elements greater come after it. This places the pivot at its final sorted position. This single subroutine is repeated recursively on the two resulting pieces. That repetition is the entire algorithm. Two classic partitioning schemes exist: Lomuto's and Hoare's. They implement this idea differently. They have different invariants, different numbers of swaps, and different failure modes on adversarial input. This article builds quicksort from the partition invariant up. We prove why the invariant guarantees correctness. We derive the average-case Θ(n log n) and worst-case Θ(n²) bounds via the recurrence they satisfy. We dissect exactly which inputs make naive pivot choices catastrophic. Understanding partitioning precisely is also a direct prerequisite for Pivot Strategies and Randomized Quicksort. It is also a prerequisite for Linear-Time Selection. Both of these reuse the same partition subroutine for different ends.
- Quicksort recursively partitions an array around a pivot, then sorts the two resulting sides independently.
- Partitioning rearranges elements in place using only O(1) extra space, achieving in-place sorting overall (O(log n) stack space for recursion).
- Lomuto's scheme is simpler to code; Hoare's scheme does fewer swaps and handles duplicates more gracefully.
- Average-case running time is Θ(n log n); worst case is Θ(n²) on already-sorted or adversarially chosen input with a fixed pivot rule.
- Correctness follows from a loop invariant maintained during partitioning, provable by induction on the scan index.
- The partition subroutine is the shared foundation for randomized quicksort and for linear-time selection algorithms.
Quicksort sorts by repeatedly partitioning an array around a pivot so that one comparison-driven rearrangement places an element at its final position and splits the problem in two.
The idea
Quicksort is built on divide-and-conquer: divide the array around a pivot, conquer each side recursively, and — unlike merge sort — there is no combine step, because after partitioning the array is already assembled correctly. Formally, given an array `A[lo..hi]`, quicksort picks a pivot element `p`, rearranges `A[lo..hi]` in place so that every element left of some index `q` is `≤ p` and every element right of `q` is `≥ p`, and then recursively sorts `A[lo..q-1]` and `A[q+1..hi]` (or `A[lo..q]` and `A[q+1..hi]`, depending on the scheme). The rearranging step is called partitioning, and it is the entire algorithmic content of quicksort. A partition procedure takes a subarray and a pivot value and returns an index that marks the boundary between the "small" and "large" regions, having achieved this boundary using only swaps within the array — no auxiliary array is allocated. This is what makes quicksort in-place: excluding the recursion stack, it uses O(1) extra memory, in contrast to merge sort's O(n) auxiliary buffer. Two partitioning schemes dominate textbooks and practice. Lomuto's partition scans left to right, always choosing the last element as pivot, and maintains an invariant tracking a "boundary of elements known to be ≤ pivot." It is simple, popular in teaching, but does more swaps and handles duplicate keys poorly. Hoare's partition — the original 1961 scheme — uses two pointers moving toward each other from both ends, swapping out-of-place pairs, and typically performs about three times fewer swaps than Lomuto's on random data. Understanding both invariants precisely, and why each is correct, is the goal of this article; strategies for choosing which element to use as the pivot are deferred to Pivot Strategies and Randomized Quicksort.
How it works
Lomuto partition. Fix the pivot as the last element `A[hi]`. Maintain an index `i` such that `A[lo..i]` are all known to be `≤ pivot`. Scan `j` from `lo` to `hi - 1`; whenever `A[j] ≤ pivot`, increment `i` and swap `A[i]` with `A[j]`. At the end, swap the pivot into position `i + 1`, which is now its correct sorted position. ``` LOMUTO-PARTITION(A, lo, hi): pivot = A[hi] i = lo - 1 // boundary: A[lo..i] <= pivot for j = lo to hi - 1: if A[j] <= pivot: i = i + 1 swap(A[i], A[j]) swap(A[i + 1], A[hi]) // place pivot in final position return i + 1 // pivot's sorted index QUICKSORT-LOMUTO(A, lo, hi): if lo < hi: q = LOMUTO-PARTITION(A, lo, hi) QUICKSORT-LOMUTO(A, lo, q - 1) QUICKSORT-LOMUTO(A, q + 1, hi) ```
Hoare partition. Fix the pivot as the first element `A[lo]` (any fixed rule works; the two-pointer logic below is what matters). Maintain two indices `i` and `j` starting just outside the subarray, and walk them toward each other: `i` advances while `A[i] < pivot`, `j` retreats while `A[j] > pivot`; when both stop, if `i < j` swap `A[i]` and `A[j]` and continue, otherwise return `j` as the split point. ``` HOARE-PARTITION(A, lo, hi): pivot = A[lo] i = lo - 1 j = hi + 1 while true: repeat i = i + 1 until A[i] >= pivot repeat j = j - 1 until A[j] <= pivot if i >= j: return j swap(A[i], A[j]) QUICKSORT-HOARE(A, lo, hi): if lo < hi: q = HOARE-PARTITION(A, lo, hi) QUICKSORT-HOARE(A, lo, q) QUICKSORT-HOARE(A, q + 1, hi) ``` Note the crucial difference in the recursive calls: Hoare's returned index `q` is not guaranteed to hold the pivot itself, so the two recursive calls are `[lo, q]` and `[q+1, hi]`, not split around `q` as a fixed point. Mixing up this detail — using Lomuto-style recursive bounds with Hoare's partition — is a classic bug that causes infinite recursion or incorrect output. The overall recursive process forms a recursion tree: each level partitions all elements present at that level in total linear time, and the tree's depth determines total work.
Complexity & correctness
Correctness of Lomuto's partition — loop invariant. At the start of each iteration of the `for` loop, three properties hold over the region `A[lo..hi]`: 1. Every element in `A[lo..i]` is `≤ pivot`. 2. Every element in `A[i+1..j-1]` is `> pivot`. 3. `A[hi]` is the pivot, untouched. Initialization: before the loop, `i = lo - 1`, so region 1 is empty and region 2 (`A[lo..j-1]`) is empty since `j = lo`; vacuously true. Maintenance: on seeing `A[j]`, if `A[j] > pivot` it belongs in region 2, and simply incrementing `j` (moving to the next iteration) extends region 2 correctly without altering region 1. If `A[j] ≤ pivot`, incrementing `i` and swapping `A[i]` with `A[j]` moves the new element into region 1's boundary while the element it displaces moves into region 2 — both regions remain internally correct. Termination: when `j = hi`, all of `A[lo..hi-1]` has been classified into regions 1 and 2. Swapping `A[i+1]` with `A[hi]` moves the pivot immediately after region 1, and since everything left of it is `≤ pivot` and everything after is `> pivot`, the pivot sits at its correct sorted position. This proves the partition is correct, and by strong induction on subarray length, the whole recursive sort is correct: each recursive call operates on a strictly smaller subarray, and the base case `lo ≥ hi` (0 or 1 elements) is trivially sorted.
Correctness of Hoare's partition follows a similar invariant: at all times, every element left of `i` is `< pivot`... actually more precisely, everything strictly left of the region being scanned that has already been finalized is `≤ pivot`, and everything strictly right is `≥ pivot`; the `repeat` loops guarantee `i` and `j` never run outside `[lo, hi]` because the pivot itself acts as a sentinel (`A[lo] = pivot` satisfies `A[i] ≥ pivot` when `i` reaches `lo`, and symmetrically for `j`). When the pointers cross (`i ≥ j`), every element at or before index `j` is `≤ pivot` and every element after `j` is `≥ pivot`, so `j` is a valid split point — though not necessarily the pivot's final resting index.
Time complexity. Partitioning a subarray of size `m` costs Θ(m): both schemes do a single linear scan (Lomuto: one pass; Hoare: two pointers each traversing the array once in total). The overall running time satisfies the recurrence ``` T(n) = T(k) + T(n - k - 1) + Θ(n) ``` where `k` is the number of elements landing left of the pivot. Worst case: if the pivot rule always picks the minimum or maximum of the current subarray (e.g., last-element pivot on already-sorted input), then `k = 0` or `k = n-1` every time, giving ``` T(n) = T(n - 1) + Θ(n) ``` which solves to Θ(n²), matching the intuition that this degenerates into something like insertion sort's worst case but with wasted comparisons. This is why quicksort's worst case is Θ(n²). Best case: if the pivot always splits the array into two equal halves, ``` T(n) = 2T(n/2) + Θ(n) ``` which, by the Master Theorem (case 2), solves to Θ(n log n). Average case: assuming the input is a random permutation (equivalently, assuming a random pivot is chosen uniformly among the `n` elements, deferred fully to Pivot Strategies and Randomized Quicksort), the expected number of comparisons `C(n)` satisfies ``` C(n) = (n - 1) + (1/n) * Σ_{k=0}^{n-1} [C(k) + C(n-1-k)] ``` Solving this recurrence (via the standard technique of multiplying through by `n`, subtracting consecutive equations, and summing a harmonic series) yields ``` C(n) = Θ(n log n) ``` with the more precise asymptotic constant `2n ln n ≈ 1.39 n log₂ n` comparisons — about 39% more comparisons than the information-theoretic optimum, which is the price paid for quicksort's low overhead and cache-friendly, in-place operation.
Space complexity. Both partition schemes use O(1) extra space per call. The recursion itself uses stack space proportional to recursion depth: Θ(log n) on average (balanced splits), but Θ(n) in the worst case (degenerate splits), which can cause stack overflow on adversarial input if not mitigated. A standard fix — recursing on the smaller half and looping (tail-call elimination) on the larger half — guarantees Θ(log n) stack depth regardless of split quality, since the smaller half can hold at most n/2 elements, halving repeatedly.
Honest tradeoffs. Quicksort is not stable (equal elements may be reordered) unless specially modified. Its worst case is worse than merge sort's guaranteed Θ(n log n), and naive pivot selection is exploitable — an adversary who knows the pivot rule can construct an input that triggers Θ(n²) behavior, a real concern for library sorts exposed to untrusted input. This is precisely the motivation for randomization and median-of-three pivoting, covered next in Pivot Strategies and Randomized Quicksort.
Worked example
Sort `A = [8, 3, 5, 4, 7, 6, 1, 2]` using Lomuto partition on the whole array (`lo = 0, hi = 7`, pivot `= A[7] = 2`).
| j | A[j] | A[j] ≤ 2? | action | array state (i shown as \ | ) |
|---|---|---|---|---|---|
| start | — | — | i = -1 | [8,3,5,4,7,6,1,2] | |
| 0 | 8 | no | skip | [8,3,5,4,7,6,1,2] | |
| 1 | 3 | no | skip | [8,3,5,4,7,6,1,2] | |
| 2 | 5 | no | skip | [8,3,5,4,7,6,1,2] | |
| 3 | 4 | no | skip | [8,3,5,4,7,6,1,2] | |
| 4 | 7 | no | skip | [8,3,5,4,7,6,1,2] | |
| 5 | 6 | no | skip | [8,3,5,4,7,6,1,2] | |
| 6 | 1 | yes | i=0, swap A[0],A[6] | [1,3,5,4,7,6,8,2] | |
| end | — | — | swap A[1],A[7] (pivot) | [1,2,5,4,7,6,8,3] |
Partition returns `q = 1`. Now `A = [1, 2, 5, 4, 7, 6, 8, 3]`, pivot `2` sits at index 1 with `A[0]=1 ≤ 2` on the left and everything from index 2 onward `> 2` on the right — invariant confirmed. Recurse left on `A[0..0]` (single element, base case, already sorted) and right on `A[2..7] = [5,4,7,6,8,3]`.
Right subcall, pivot `= A[7] = 3` (indices 2..7):
| j | A[j] | ≤ 3? | action |
|---|---|---|---|
| 2 | 5 | no | skip |
| 3 | 4 | no | skip |
| 4 | 7 | no | skip |
| 5 | 6 | no | skip |
| 6 | 8 | no | skip |
| end | — | — | swap A[2],A[7] → pivot to index 2 |
Result: `A[2..7] = [3,4,7,6,8,5]`, pivot `3` at index 2 — but wait, recompute: after the scan, `i = 1` (relative boundary at `lo-1 = 1`, no increments occurred), so pivot swaps into `A[2]`. The subarray becomes `[3, 4, 7, 6, 8, 5]`. Left of index 2 is empty (correct, nothing `≤ 3` besides pivot), right is `[4,7,6,8,5]`, all `> 3` ✓. Recurse on `A[3..7] = [4,7,6,8,5]`, pivot `= 5`:
| j | A[j] | ≤5? | action |
|---|---|---|---|
| 3 | 4 | yes | i=3(local), swap A[3],A[3] (no-op) |
| 4 | 7 | no | skip |
| 5 | 6 | no | skip |
| 6 | 8 | no | skip |
| end | — | — | swap A[4], A[7] |
Before swap: `[4,7,6,8,5]` → after placing pivot: `[4,5,6,8,7]`. Pivot `5` lands at index 4 (global), left `{4}` all `≤5`, right `{6,8,7}` all `>5` ✓. Continue recursing on `[6,8,7]` (indices 5..7), pivot `=7`: scan finds `6 ≤ 7` (swap into place, no-op), `8 > 7` (skip), then pivot swaps to index 6: result `[6,7,8]`. Base cases finish the rest. Final array: `[1, 2, 3, 4, 5, 6, 7, 8]` — sorted, confirming the algorithm terminates correctly even though the chosen pivots (always the last element) were far from ideal, producing a moderately unbalanced but still polynomial-time recursion tree in this instance.
Common pitfalls & traps
| Pitfall | Why it happens | Fix |
|---|---|---|
| Sorted/reverse-sorted input causes Θ(n²) with last-element pivot | Every partition splits off just one element | Randomize pivot or use median-of-three (Pivot Strategies and Randomized Quicksort) |
| Mixing Hoare's returned index with Lomuto-style recursion (`q-1`, `q+1`) | Hoare's `q` is a split point, not the pivot's final index | Recurse on `[lo, q]` and `[q+1, hi]` for Hoare; verify no infinite loop when `q = hi` |
| Off-by-one in Lomuto boundary initialization (`i = lo` instead of `lo - 1`) | Miscounts the "≤ pivot" region, corrupting the invariant | Always initialize `i` one below `lo` so the empty region is well-defined |
| Many duplicate keys degrade Lomuto to Θ(n²)-like imbalance | All duplicates equal to pivot go to one side | Use a three-way (Dutch national flag) partition for arrays with many duplicates |
| Deep recursion causing stack overflow on large inputs | Worst-case Θ(n) recursion depth | Recurse on smaller partition, iterate (tail-eliminate) on the larger one |
| Forgetting quicksort is not stable | Equal keys can be swapped past each other during partitioning | Use a stable sort (merge sort, or tagged indices) when stability is required |
Pioneers & history
Origins · 1 minC. A. R. (Tony) Hoare and how this was discovered
Hoare devised quicksort almost by accident: tasked with sorting words for a Russian-to-English translation dictionary lookup, he realized a partition-based recursive scheme could outperform the sorting methods then in common use. He published the algorithm in 1961, alongside the two-pointer partitioning scheme that now bears his name, and later developed Hoare logic, a formal system for proving program correctness — the very style of invariant-based reasoning used above to verify quicksort itself.
Origins · 1 minhow this was discovered
Where this matters
Quicksort and its descendants power sorting in nearly every mainstream runtime. C's standard library `qsort`, many implementations of C++'s `std::sort` (via introsort, a quicksort/heapsort hybrid), and array sorting in numerous scripting languages all trace their lineage to Hoare's partition. Database engines use partition-based sorting for in-memory intermediate result sets where auxiliary memory is scarce. The partitioning subroutine itself, independent of full sorting, is reused directly in quickselect for finding the k-th smallest element in expected linear time — the subject of Linear-Time Selection — and in randomized algorithms more broadly, where the same divide-by-a-random-pivot idea recurs. Understanding the Lomuto and Hoare invariants precisely is what allows engineers to reason about worst-case denial-of-service risks, tune pivot strategies for real-world data distributions, and safely combine quicksort with fallback algorithms in production-grade hybrid sorts.
:::quiz[In Lomuto's partition, what does the invariant guarantee about A[lo..i] at any point during the scan?]
- All elements are equal to the pivot
- All elements are ≤ the pivot ✓
- All elements are unsorted
- The pivot is always at index i
Ask the tutor: How does randomizing the pivot choice formally convert quicksort's average-case guarantee into an expected-case guarantee for any input?
Why does quicksort have Θ(n²) worst case if it is supposedly one of the fastest sorting algorithms?
Quicksort's speed comes from cheap, cache-friendly in-place partitioning, not from a guaranteed balanced split. If the chosen pivot is always the smallest or largest remaining element — which happens on sorted input with a naive last-element pivot rule — each partition only removes one element from consideration, producing a recursion depth of n and Θ(n²) total comparisons. Randomized pivot selection or median-of-three heuristics make this pathological case astronomically unlikely on any fixed input, restoring expected Θ(n log n) behavior. That is precisely the subject explored under Pivot Strategies and Randomized Quicksort.
What's the practical difference between Lomuto's and Hoare's partition schemes?
Lomuto's partition is simpler to implement and reason about, using a single index and one boundary invariant, but it performs roughly three times more swaps on average and handles arrays with many duplicate keys poorly, sometimes causing unnecessary imbalance. Hoare's original partition uses two pointers converging from both ends, does fewer swaps, and is more efficient in practice, but its returned split index does not mark the pivot's final position, which requires careful, different recursive bounds. Most textbooks teach Lomuto's first for clarity, then introduce Hoare's for performance.
Is quicksort a stable sorting algorithm?
No, standard quicksort is not stable: partitioning can reorder equal-keyed elements relative to each other, since swaps are based purely on comparison outcomes without tracking original positions. This contrasts with merge sort, which can be implemented stably by always taking from the left subarray on ties. If stability is required — for example, sorting records by one field while preserving order from a previous sort on another field — a different algorithm, or a modification that tags elements with original indices as tiebreakers, is needed.
How does quicksort achieve in-place sorting, and what does "in-place" really mean here?
In-place means the algorithm uses only O(1) extra memory beyond the input array itself, aside from the recursion's call stack. Partitioning achieves this by rearranging elements through swaps within the same array rather than copying into new storage, unlike merge sort's explicit auxiliary buffer for merging. The recursion stack does consume additional memory proportional to recursion depth — Θ(log n) on average, Θ(n) worst case — so quicksort is in-place in the sense of avoiding auxiliary arrays, though not entirely memory-free.
Why does the average-case analysis assume a random input or random pivot, and is that assumption realistic?
The Θ(n log n) average-case bound is derived under the assumption that the input is a uniformly random permutation, or equivalently, that the pivot is chosen uniformly at random among the current subarray's elements. Real-world data is rarely a uniformly random permutation — it often has partial order, duplicates, or adversarial structure — so relying on "average-case" input behavior is risky. This is exactly why practical implementations randomize the pivot choice explicitly: it converts the average-case guarantee into an expected-case guarantee that holds for any fixed input, with high probability, regardless of the input's actual distribution.
Can quicksort's worst case be eliminated entirely?
Not while remaining an in-place, comparison-based sort with quicksort's exact partitioning structure — some input will always trigger Θ(n²) behavior for any fixed, deterministic pivot rule, since an adversary can reverse-engineer that rule. However, hybrid algorithms like introsort sidestep this: they run quicksort but monitor recursion depth, switching to heapsort (guaranteed Θ(n log n)) if depth exceeds a logarithmic threshold, and switching to insertion sort for small subarrays. This gives the practical speed of quicksort with a guaranteed worst-case bound, which is why most modern library sorts use such hybrids.
How does partitioning relate to the linear-time selection algorithm (quickselect)?
Quickselect reuses the exact same partition subroutine as quicksort but recurses into only one side — the side known to contain the k-th smallest element — rather than both. Since it discards one partition entirely instead of recursing on it, its expected running time recurrence solves to Θ(n) rather than Θ(n log n), because the total work across recursive calls decreases geometrically. This technique, along with worst-case-linear variants using guaranteed-good pivots, is developed fully in Linear-Time Selection.