Quicksort
Quicksort explained: how partitioning around a pivot sorts in place, why average-case performance beats merge sort, and when worst-case behavior strikes.
Quicksort is a divide-and-conquer sorting algorithm that picks a pivot element, partitions the array so smaller values sit left and larger values right, then recursively sorts each side. It runs in linearithmic time on average, sorts in place, and remains the default sorting strategy in many standard libraries.
How partitioning works
The heart of quicksort is the partition step. Choose a pivot — the first element, a random element, or the median of three candidates — then rearrange the segment so every element below the pivot precedes it and every element above follows it. Lomuto's scheme scans once while maintaining a boundary index; Hoare's original scheme walks two pointers inward from opposite ends and swaps out-of-place pairs, performing fewer swaps on average. Either way, the pivot finishes in its final sorted position, and the two sides become independent subproblems solved by recursion. The base case — a segment of zero or one elements — is already sorted.
partition(a, lo, hi):
pivot = a[hi]
i = lo
for j in lo..hi-1:
if a[j] <= pivot:
swap(a[i], a[j])
i += 1
swap(a[i], a[hi])
return i
Average-case versus worst-case complexity
Quicksort's average running time is linearithmic: each level of recursion processes all n elements during partitioning, and the recursion depth averages log n because pivots typically split segments roughly in half. The vocabulary for these claims is Big-O notation. The worst case — quadratic time — strikes when pivots are consistently extreme, as with already-sorted input and a first-element pivot, which produces lopsided partitions of size one and n minus one at every level. Randomized pivot choice makes this adversarial case vanishingly unlikely, which is why production implementations randomize or use median-of-three selection.
Quicksort versus merge sort
Merge sort is quicksort's closest rival: both divide and conquer in linearithmic time, but merge sort guarantees that bound while requiring linear extra memory for merging. Quicksort sorts in place with only logarithmic stack space and enjoys better cache locality, since partitioning scans contiguous memory sequentially. That locality is why quicksort usually wins wall-clock benchmarks despite the weaker guarantee. Merge sort keeps its crown where stability matters — preserving the order of equal elements — or where guaranteed performance and external sorting of data larger than memory are required.
Practical optimizations
Real implementations refine the textbook algorithm. Small subarrays, often under ten to twenty elements, switch to insertion sort, whose low overhead beats recursion there. Recursing into the smaller side first bounds stack depth at logarithmic size. Three-way partitioning groups equal keys together, turning inputs with many duplicates from a weakness into near-linear time. Introsort — used in C++ standard sort routines — starts as quicksort but switches to heapsort if recursion depth exceeds a threshold, guaranteeing linearithmic worst case. Once sorted, data supports logarithmic lookup via binary search, completing the pipeline from raw input to searchable order.
Tags
algorithms divide and conquer quicksort sorting
Related articles
- Merge Sort
- Prime Numbers and the Sieve of Eratosthenes
- P vs NP
- How Dating App Algorithms Actually Work
- Dating App Shadowbans: What They Are and How to Actually Test
- How ATS Resume Screening Actually Works