quicksort

Partition around a pivot, then recurse.

best: O(n log n)
average: O(n log n)
worst: O(n²)
space: O(log n)

reference implementation

verified source·read-only

loading editor

brief

Quicksort picks the last element as a pivot, sweeps the range once, and moves everything smaller to the left until the pivot lands in its final position. The two sides are then sorted independently. The partition is linear, so the recursion depth decides everything: balanced splits give O(n log n), while a last-element pivot on sorted or reversed input splits off one element at a time and degrades to O(n²).

the math

The partition invariant

During the sweep, everything in $a[lo..i-1]$ is $\le$ pivot and everything in $a[i..j-1]$ is $>$ pivot.
The index $i$ is the boundary where the next small element will be placed.
When $j$ reaches $hi$ the invariant has consumed the whole range except the pivot itself.

The pivot lands in place

The last element is marked as the pivot before the sweep.
After the sweep it is swapped into position $i$ , which is its final index.
Only then are the left and right subranges sorted, independently of each other.

Counting comparisons

Each partition compares every other element of its range against the pivot exactly once.
Random input averages $\approx 1.39\, n \log_2 n$ comparisons: the constant is worse than merge sort's, which is why the in-place partition still competes.
Every element is compared once per partition it belongs to, so the total is the sum of the range sizes minus one per partition.

Worst case: already ordered

With the last element as pivot, sorted or reversed input keeps splitting off a single element.
The ranges shrink by one instead of halving, so comparisons reach $\frac{n(n-1)}{2} = O(n^2)$ .
A random or median-of-three pivot fixes this in practice; the recursion depth is the price of the in-place partition.

Duplicate keys

Equal keys satisfy the $\le$ test, so they all move to the left partition.
A run of equal keys is therefore not split in half — Lomuto's scheme degrades on duplicate-heavy input.
Three-way partitioning (Dutch national flag) is the standard fix when duplicates are common.

▍ Quicksort · small

requesting trace

· decoding trace

· replaying events

· mounting renderer

0/0

fun facts

Tony Hoare developed quicksort in 1959 while working on machine translation of Russian text, and published it in 1961.
Hoare received the Turing Award in 1980; quicksort is still the default in many standard libraries.
The last-element pivot is why sorted input is the worst case: every partition peels off one element and comparisons become n(n − 1)/2.
Most C++ standard libraries implement std::sort as introsort — quicksort that switches to heapsort when the recursion gets too deep — though the standard does not mandate the algorithm.

quicksortstep 0/00%spaceplay←→steppprojectorrreset