Quicksort is a divide-and-conquer sorting algorithm that picks one element as a pivot, rearranges the data so that smaller elements come before it and larger ones after it, and then sorts both parts recursively. Among comparison-based algorithms in programming, it is valued for its average running time of O(n log n), its very small constant factors and the fact that it sorts in place, needing only O(log n) additional memory for recursion in a careful implementation.
Quicksort was introduced by Tony Hoare around 1960 and remains one of the most widely used sorting algorithms. Variants of it form the core of the default sort routines for primitive data in many standard libraries, usually combined with safeguards against its worst case of O(n²).
How quicksort partitions and recurses
Every round of quicksort consists of three steps: choose a pivot, partition the range, recurse on the two resulting subranges. After partitioning, the pivot is in its final sorted position, so it never moves again, and the two sides can be sorted independently.
- Select a pivot element from the current range using a pivot strategy.
- Partition the range so that elements less than the pivot precede it and greater elements follow it.
- Apply quicksort recursively to the left part and to the right part.
- Stop when a range has zero or one element, or hand small ranges to insertion sort.
All real work happens during partitioning; there is no merge step. This is the essential difference from merge sort, which splits trivially and does its work while combining. Because partitioning only swaps elements within the array, quicksort has excellent cache locality and moves data efficiently through memory.
Partition schemes and pivot selection
Two classic partition schemes exist, and they behave differently on real data. The Lomuto scheme is simple to write and teach, while the Hoare scheme performs about three times fewer swaps on average and copes better with repeated values.
| Scheme | How it works | Strengths and weaknesses |
|---|---|---|
| Lomuto | One index scans, smaller elements swapped forward | Simple, but many swaps and poor with duplicates |
| Hoare | Two indexes move inward and swap out-of-place pairs | Fewer swaps, pivot not fixed in place at the end |
| Three-way (Dutch national flag) | Splits into less, equal and greater regions | Handles many duplicate keys efficiently |
| Dual-pivot | Two pivots create three partitions | Fewer memory accesses in practice |
The pivot strategy decides whether partitions are balanced. A good pivot splits the range roughly in half; a poor pivot, such as the smallest element, produces one empty side and one side almost as large as the original range.
| Strategy | Effect | Risk |
|---|---|---|
| First or last element | Cheap to compute | Quadratic time on sorted or reversed input |
| Random element | Expected O(n log n) on any input | Bad luck possible, but extremely unlikely |
| Median of three | Samples first, middle and last elements | Crafted inputs can still defeat it |
| Ninther or median of medians | Better pivot estimates on large ranges | Extra cost per partition |
Time and space complexity of quicksort
The running time of quicksort depends on how evenly each partition splits the data. With balanced splits, the recursion depth is about log₂ n levels, and each level does linear work, which gives O(n log n). On average over random inputs, quicksort makes about 1.39 n log₂ n comparisons.
| Case | Time | When it occurs |
|---|---|---|
| Best case | O(n log n) | Pivots split ranges evenly |
| Average case | O(n log n) | Random input or randomized pivots |
| Worst case | O(n²) | Pivots repeatedly pick extreme values |
| Space, careful version | O(log n) | Recursing on the smaller side first |
| Space, naive version | O(n) | Unbalanced recursion on the larger side |
The space bound deserves attention. A naive implementation can reach a recursion depth of n on bad input and overflow the call stack. Recursing into the smaller partition and looping over the larger one keeps the stack depth at O(log n) in every case.
Quicksort compared with other sorting algorithms
Quicksort is usually the fastest general-purpose comparison sort in practice, but it is not the right choice for every situation. The comparison below shows where its neighbors win.
| Algorithm | Average and worst time | Stable | Extra memory |
|---|---|---|---|
| Quicksort | O(n log n) and O(n²) | No | O(log n) |
| Merge sort | O(n log n) and O(n log n) | Yes | O(n) |
| Heapsort | O(n log n) and O(n log n) | No | O(1) |
| Insertion sort | O(n²) and O(n²) | Yes | O(1) |
| Bubble sort | O(n²) and O(n²) | Yes | O(1) |
Quicksort is not stable, meaning equal elements may change their relative order. When stability matters, for example when sorting records first by date and then by name, merge sort or Timsort is the usual choice. When a guaranteed worst case matters more than average speed, heapsort or merge sort is safer.
Practical implementations and pitfalls
Production implementations rarely use textbook quicksort alone. Introsort starts with quicksort, switches to heapsort when recursion grows deeper than about 2 log₂ n, and finishes small ranges with insertion sort. This keeps the speed of quicksort while guaranteeing O(n log n) in the worst case.
- Switch to insertion sort for small ranges, typically below about 10 to 32 elements.
- Randomize or sample the pivot to avoid quadratic behavior on sorted input.
- Use three-way partitioning when the data contains many equal keys.
- Guard against adversarial input in services that sort user-supplied data.
- Do not rely on stability, because equal elements can be reordered.
The simple explanation
Imagine sorting a pile of exam papers by score. You pick one paper, say with a score of 70, and make two piles: everything below 70 on the left, everything above on the right. The paper with 70 now sits exactly where it belongs. Then you repeat the same trick on each smaller pile until every pile has just one paper.
That is quicksort. It is usually very fast, because each step cuts the problem into smaller pieces. It only becomes slow when the chosen paper keeps being the lowest or highest score, which is why good implementations choose it carefully.
How it is used in practice
A backend developer at a logistics company needs to sort about five million shipment records by numeric tracking weight every hour to build a report. A simple bubble sort would require on the order of trillions of comparisons, which is completely impractical.
The developer uses the standard library sort for an array of primitive numbers, which in that language is a dual-pivot quicksort variant. The sort finishes in well under a second on a normal server, because it performs roughly n log n comparisons and works within the array without copying it.
Later, the report must keep records with equal weights in their original arrival order. Since quicksort is not stable, the developer switches that step to the stable object sort, and the report becomes both fast and correctly ordered.