Quicksort is a comparison-based in-place sorting algorithm that partitions an array around a chosen pivot element — placing all smaller elements before the pivot and all larger elements after — then recursively sorts each partition, achieving Θ(n log n) expected time with O(log n) space.
Quicksort picks a pivot element, moves everything smaller to its left and everything larger to its right, then recursively sorts each side — and it is typically the fastest comparison sort in practice.
The pivot idea
Quicksort's key step is partitioning: pick one element as the pivot, then rearrange the array so that every element smaller than the pivot comes before it, and every element larger comes after it. The pivot is now in its final sorted position. Recursively sort the left part and the right part.
def quicksort(arr, lo=0, hi=None):
if hi is None: hi = len(arr) - 1
if lo < hi:
p = partition(arr, lo, hi)
quicksort(arr, lo, p - 1) # sort left of pivot
quicksort(arr, p + 1, hi) # sort right of pivot
def partition(arr, lo, hi):
pivot = arr[hi] # last element as pivot
i = lo - 1 # boundary of elements <= pivot
for j in range(lo, hi):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i+1], arr[hi] = arr[hi], arr[i+1] # pivot to final position
return i + 1
arr = [5, 2, 8, 1, 9, 3]
quicksort(arr)
print(arr) # [1, 2, 3, 5, 8, 9]Complexity
| Case | Time | Space |
|---|---|---|
| Best | Θ(n log n) | O(log n) |
| Average | Θ(n log n) | O(log n) |
| Worst | Θ(n²) | O(n) |
Worst case occurs when the pivot is always the smallest or largest element — producing maximally unbalanced partitions. On already-sorted input with the last element as pivot, every partition produces one empty subarray and one of size n-1: T(n) = T(n-1) + Θ(n) = Θ(n²).
In-place: a practical advantage
Quicksort sorts within the array — it only needs O(log n) stack space for the recursive calls, compared to merge sort's O(n) for the merge buffer. This better cache utilisation is a primary reason quicksort is typically faster in practice than merge sort despite the worst-case difference.
Pivot selection strategies
Last element: simplest; degrades on sorted/reverse-sorted input. Random pivot: randomly selected each call; makes worst case extremely unlikely — expected O(n log n) on any input. Median-of-three: pick the median of first, middle, last element; better than last-element for common patterns. Ninther (median of medians of 3 groups): used in some production implementations.
Introsort: quicksort + heapsort
Production sort implementations (C++ std::sort, Java primitives, .NET) use introsort (David Musser, 1997): start with quicksort; if the recursion depth exceeds 2⋅log₂n (indicating a bad partition pattern), switch to heapsort which guarantees O(n log n) worst case. This gives quicksort's average-case speed with a guaranteed O(n log n) worst case. Java's Arrays.sort() for primitive types uses dual-pivot quicksort (Yaroslavskiy, 2009) — two pivots divide into three partitions — which is faster in practice than single-pivot quicksort.
Lomuto vs. Hoare partition schemes
Two standard partition implementations. Lomuto (shown above): pivot at end, single index i tracking the boundary. Simple to implement and understand. Does 3× more swaps than Hoare on average. Hoare: two pointers scanning from both ends inward, swapping when they cross — fewer swaps, slightly better cache behaviour, but the pivot ends up between the two partitions (not necessarily at index lo+1). Hoare is faster but trickier to implement correctly.
def hoare_partition(arr, lo, hi):
pivot = arr[lo] # first element as pivot
i, j = lo - 1, hi + 1
while True:
i += 1
while arr[i] < pivot: i += 1 # find element >= pivot from left
j -= 1
while arr[j] > pivot: j -= 1 # find element <= pivot from right
if i >= j: return j # partitions don't overlap
arr[i], arr[j] = arr[j], arr[i]Expected O(n log n) with random pivot: formal analysis
With a uniformly random pivot choice, the expected number of comparisons is 2n ln n ≈ 1.386 n log₂ n (CLRS §7.4). Proof using indicator random variables: let Xij = 1 if elements zi and zj (i < j) are compared. Pr[Xij = 1] = 2/(j-i+1) — they are compared only if one of them is chosen as pivot before any element between them. E[total comparisons] = ∑ 2/(j-i+1) for all i < j = 2n ln n + O(n).
Dual-pivot quicksort
Java's Arrays.sort for primitive types (since Java 7) uses dual-pivot quicksort (Vladimir Yaroslavskiy, 2009). Choose two pivots p1 ≤ p2. Partition into three sections: elements < p1, elements between p1 and p2, elements > p2. Recursively sort each section. In practice 10–15% faster than single-pivot quicksort because the three-way partitioning reduces comparisons on typical data distributions. Expected comparisons: 1.9 n log₂ n vs. 2 n log₂ n for single-pivot.
Cormen, T. H. et al. (2022). CLRS (4th ed.), §7 — Quicksort (Lomuto partition, expected analysis). Hoare, C. A. R. (1962). "Quicksort." Computer Journal 5(1), 10–16. Musser, D. (1997). "Introspective sorting and selection algorithms." SPE 27(8). Yaroslavskiy, V. (2009). Dual-pivot quicksort. OpenJDK proposal.