QuickSort / QuickSelect

Partition an array around a pivot so the pivot lands in its final place. Sort both sides for quicksort, or follow only the side that holds index k for quickselect, which finds the k-th value in O(n) expected time.

Overview

The idea

Quicksort picks one value, the pivot, and partitions the array: everything smaller goes to the pivot's left and everything larger to its right. After that one pass the pivot is in its final sorted position and never moves again. Then the same is done to the left part and the right part. Tony Hoare developed it in 1959 and published it in 1961.

Quickselect is the same partition with one change: instead of sorting both sides, follow only the side that contains the index you want. That finds the k-th smallest value without sorting the rest.

After a partition — recurse on both sides — continue on one side
Expected time — O(n log n) — O(n)
Worst case — O(n²) — O(n²)
Extra space — O(log n) stack, recursing on the smaller side first — O(1) as a loop
Stable — no — changes the array

The Lomuto partition

The simplest partition, attributed to Nico Lomuto and made popular by Jon Bentley's Programming Pearls. The pivot is the last value. Index i marks the end of the small values; j scans everything else. When a[j] is at most the pivot, i moves up and a[i] and a[j] swap. At the end the pivot swaps into i + 1.

0 — 3 — at most 4: i = 0, swap a[0] with itself — 0 — 3 2 1 5 6 4
1 — 2 — at most 4: i = 1, swap with itself — 1 — 3 2 1 5 6 4
2 — 1 — at most 4: i = 2, swap with itself — 2 — 3 2 1 5 6 4
3 — 5 — larger: leave — 2 — 3 2 1 5 6 4
4 — 6 — larger: leave — 2 — 3 2 1 5 6 4
end — swap pivot into index 3 — 3 2 1 4 6 5

The pivot is now at index 3, its final position. Lomuto is short and easy to get right, but when every value equals the pivot, every a[j] passes the test, i ends next to the pivot, and the split is n - 1 against 0. Equal values are its weak point.

The Hoare partition

Hoare's own scheme scans from both ends. i moves right past values smaller than the pivot, j moves left past values larger, and the two stop at a pair that is on the wrong sides, which they swap. When the scans cross, the partition is done. On average it does about three times fewer swaps than Lomuto, and on all-equal input it stops on every value, so the split stays balanced.

The trace below uses the first value, 5, as the pivot on [5, 3, 8, 4, 2, 7].

0 (5) — 4 (2) — swap — 2 3 8 4 5 7
2 (8) — 3 (4) — swap — 2 3 4 8 5 7
3 (8) — 2 (4) — crossed: return j = 2 — 2 3 4 8 5 7

The left part is indexes 0 to 2 and the right part is 3 to 5. The pivot is not necessarily at index j, so the recursion is on lo..j and j + 1..hi, and it must not exclude the pivot the way Lomuto's does. Both schemes are O(n) per partition.

Choosing the pivot

The cost of quicksort is the depth of the recursion. A pivot near the median splits the array in half and gives log2 n levels. A pivot that is the smallest or largest value peels off one element and gives n levels.

Always the last (or first) value — O(n²): every split is n - 1 against 0 — the classic mistake
Middle index — fine on sorted input — still beatable by a crafted input
Median of three (first, middle, last) — good on sorted and reversed input — cheap
Random index — O(n log n) expected on every input — no input can be crafted against it
Median of medians — O(n log n) worst case — large constant factor; used as a fallback

The gap is real. Sorting 1,000 values that are already in order with a fixed last pivot costs 1000 times 999 / 2 = 499,500 comparisons, about fifty times the roughly 10,000 of n log2 n. A random pivot on the same input gives a recursion depth of about 21 on average (17 to 29 over 200 seeded runs) instead of 999.

Keeping the stack small

The recursion depth is also memory. Recurse on the smaller side first and loop on the larger side: the smaller side is at most half the range, so the stack never grows past log2 n frames even when the splits are bad.

Quickselect: the k-th value without sorting

The array is partitioned once. If the pivot landed on index k, that value is the answer. If k is to the left, repeat on the left part only; otherwise on the right part only. Everything on the other side is never touched again.

The trace finds the second largest of [3, 2, 1, 5, 6, 4], which is the value at sorted index 4.

0 to 5 — 4 — 3 2 1 4 6 5 — 3 — 4 is to the right: range 4 to 5
4 to 5 — 5 — 3 2 1 4 5 6 — 4 — equals k: answer 5

With a random pivot the range shrinks by a constant fraction on average, so the work is about n + n/2 + n/4 + ..., which is under 2n: O(n) expected. The worst case is still O(n²).

Sort, then index — O(n log n) — depends on the sort — simplest
Min-heap of size k — O(n log k) — O(k) — works on a stream, firm bound
Quickselect, random pivot — O(n) expected, O(n²) worst — O(1) as a loop — changes the array
Median of medians — O(n) worst case — O(n) — slower in practice

Median of medians (Blum, Floyd, Pratt, Rivest and Tarjan, 1973) picks the pivot by taking the median of each group of five values, then the median of those medians. That pivot has at least 3n/10 values on each side, which gives the recurrence T(n) is at most T(n/5) + T(7n/10) + cn, and the two fractions add up to less than one, so T(n) is O(n). Its constants are large, so real libraries use random pivots and fall back to it only when the recursion goes too deep, a scheme called introselect.

Many equal values: partition three ways

When the array has few distinct values, a two-way partition wastes work on values equal to the pivot. A three-way partition keeps three regions: below, equal and above, using the indexes low, mid and high, and never revisits the equal region. This is the Dutch national flag method from Edsger Dijkstra, and it is the whole solution to Sort Colors.

below the pivot — swap a[low] and a[mid], then low + 1 and mid + 1
equal to the pivot — mid + 1
above the pivot — swap a[mid] and a[high], then high - 1; mid stays

The Two Pointers topic traces it step by step.

What the libraries do

Java Arrays.sort(int[]) — Dual-Pivot Quicksort by Yaroslavskiy, Bentley and Bloch
Java Arrays.sort(Object[]) — a stable merge sort adapted from Timsort, since objects need stability
C++ std::sort in libstdc++ and libc++ — introsort (Musser, 1997): quicksort that switches to heapsort past a depth of 2 log2 n and to insertion sort on small ranges
Python sorted — Timsort, a merge sort; not quicksort
JavaScript Array.prototype.sort — the language only requires a stable sort (since ES2019); V8 uses Timsort

So quicksort is the usual choice for primitive arrays in memory, where it is fast and stability does not matter, and merge sort is the choice where stability does.

What you will be able to do

Write a partition, Lomuto or Hoare, and say where the pivot ends up.
Explain why the pivot choice decides the depth, and what a random pivot buys.
Bound the stack at O(log n) by recursing on the smaller side.
Find the k-th largest value with quickselect and compare it with a heap.
Handle arrays with many duplicates with a three-way partition.

When to use it

Sorting an array in memory when stability does not matter and a random pivot is acceptable
The k-th smallest or largest value, or the top k in any order, in O(n) expected time
In-place grouping around a value: Sort Colors, move smaller values before larger ones
Arrays with many duplicates, using a three-way partition
A partial sort: everything before index k smaller, everything after it larger, with no order inside the parts

More Coding & DSA topics

Start free on Cariara · Coding problems · System design studio