Quick sort
Scenario
You are sorting a deck of 52 cards on a small table. There is no room to lay out a second pile for merging. You pick one card, say the 7 of hearts, and make two stacks: everything lower than it on the left, everything higher on the right.
Is the 7 of hearts now in its final place, and what is left to do?
Overview
A divide-and-conquer sort that partitions the array around a pivot in place, then recursively sorts the part before the pivot and the part after it.
It is the standard way to sort an array in memory: `O(n log n)` on average, tiny constant factors, and almost no extra memory.
Where used: Library sorts for primitive arrays (C++ `std::sort` is introsort, a quick sort hybrid; Java sorts primitive arrays with a dual-pivot quick sort), Systems where allocating a second buffer is costly
Why it exists
Problem: Merge sort is reliably `O(n log n)`, but every merge needs a second array the size of the input. On big in-memory arrays the copying costs time, and the extra memory is not always there.
Naive approach: Use an in-place `O(n^2)` sort such as insertion sort and accept that it gets slow quickly as the data grows.
Better idea: Do the splitting work before the recursion instead of after it. Pick a pivot and rearrange the array in place so everything smaller is on its left and everything larger is on its right. The pivot is now in its final position, and the two sides are independent smaller sorting problems.
Why learn this
- It is one of the two sorts every interviewer expects you to be able to write and analyse (the other is merge sort).
- It is the cleanest example of expected time versus worst-case time, and of fixing a worst case with randomness.
- Its partition step is reused in quickselect and in many in-place array problems.
Mental model
Pick one element, put it exactly where it belongs by sorting everything else around it into 'smaller' and 'larger', then do the same to each side.
After one partition pass the pivot never moves again. What is left is two smaller arrays that do not interact: nothing on the left needs to be compared with anything on the right. Sorting is just partitioning, repeated until every range has 0 or 1 elements. Merge sort does its work on the way back up the recursion; quick sort does it on the way down, which is why it needs no merge buffer.
Repeated decision: Is this element smaller than the pivot? If so, it belongs in the left group.
Deep dive
Quick sort has three steps on a range `[lo, hi]`.
- Choose a pivot (here, the last element).
- Partition: rearrange the range so every element smaller than the pivot comes before it and every other element comes after it. The pivot ends up at its final index `p`.
- Recurse on `[lo, p - 1]` and `[p + 1, hi]`. A range with 0 or 1 elements is already sorted, so that is the stop condition.
The pivot is excluded from both recursive calls. It is already in the right place, and including it again is the classic way to recurse forever.
A worked run on `[7, 2, 9, 4, 3, 8, 6]`, with the last element as the pivot and a boundary `i` that marks where the 'smaller than pivot' group ends.
Pivot is `6`. Scan from the left. `7` is not smaller. `2` is, so swap it to the boundary: `[2, 7, 9, 4, 3, 8, 6]`. `9` is not. `4` is: `[2, 4, 9, 7, 3, 8, 6]`. `3` is: `[2, 4, 3, 7, 9, 8, 6]`. `8` is not. Finally swap the pivot into the boundary slot:
[2, 4, 3, 6, 9, 8, 7]
`6` is now at index 3, its final place. Everything before it is smaller and everything after it is larger, but each side is still unsorted. Recurse on `[2, 4, 3]` and `[9, 8, 7]`. After those two finish you get `[2, 3, 4, 6, 7, 8, 9]`. No merge step was needed, because the sides were already in the right places relative to each other.
How fast is it? Each level of the recursion partitions every element once, which is `O(n)` work per level. If each pivot lands near the middle, the recursion is about `log n` levels deep and the total is `O(n log n)`.
If the pivot is the smallest or largest element every time, one side is empty and the other has `n - 1` elements. The recursion becomes a chain `n` deep and the total is `n + (n - 1) + ... + 1`, which is `O(n^2)`. With 'last element as pivot', an already sorted array does exactly this, and sorted or nearly sorted input is very common in practice.
The fix is to make a bad pivot unlikely, not impossible:
- Random pivot: swap a randomly chosen element into the pivot slot before partitioning. No fixed input is bad any more; the expected time is `O(n log n)` for every input.
- Median of three: use the median of the first, middle and last elements. It defeats sorted and reverse-sorted input cheaply.
Neither one removes the `O(n^2)` worst case in theory. They make it very unlikely.
Two refinements are worth knowing.
Equal keys. With a strict 'smaller than pivot' test, an array where every value is the same puts nothing on the left, so it degrades to `O(n^2)`. A three-way partition fixes it: split the range into smaller than, equal to, and greater than the pivot, and recurse only on the first and last groups. It is the same idea as sorting an array of 0s, 1s and 2s in one pass, and an array with many duplicates then sorts in close to `O(n)`.
The usual way to do it keeps three regions and one scanner `i`: everything before `lt` is smaller, everything from `gt` to the end is larger, and everything from `lt` up to `i` equals the pivot. Start with `lt = lo`, `i = lo` and `gt = hi`.
while i <= gt:
if a[i] < pivot: swap a[i], a[lt]; lt += 1; i += 1
elif a[i] > pivot: swap a[i], a[gt]; gt -= 1
else: i += 1
When a larger element is swapped to the end, `i` does not move, because the element that arrived at `i` has not been looked at yet.
Stack depth. The recursion uses stack space equal to its depth, which is `O(log n)` on a good run but up to `O(n)` on a bad one. Recurse into the smaller side and loop on the larger side. The smaller side has at most half the elements, so the depth never exceeds `log2(n)` even when the split is bad.
Production sorts combine these ideas. Introsort (used by C++ `std::sort`) runs quick sort, counts the recursion depth, and switches to heap sort if the depth passes about `2 * log2(n)`, which caps the worst case at `O(n log n)`.
Quick sort versus merge sort:
- Time: both `O(n log n)` on average; quick sort is `O(n^2)` in the worst case, merge sort never is.
- Extra memory: quick sort `O(log n)` for the stack (with the smaller-side rule), merge sort `O(n)` for the merge buffer.
- Stability: merge sort is stable. Quick sort is not, because partition swaps move equal elements past each other.
- Speed in memory: quick sort usually wins on arrays. It scans memory in order and does no allocation.
That is why languages sort numbers with a quick sort variant and often sort objects with a stable merge-based sort. Python's built-in sort is Timsort, a stable merge and insertion hybrid.
Key points
- Invariant: After partitioning, the pivot is at its final sorted index. Everything before it is smaller, everything after it is not smaller. The two sides can be sorted independently.
- Complexity: Average `O(n log n)`, worst case `O(n^2)`. Extra space `O(log n)` for the stack if you recurse into the smaller side first, `O(n)` if you do not.
- In place, not stable: No merge buffer is needed, but partition swaps reorder equal elements, so quick sort is not stable.
- Pivot choice decides the speed: A pivot near the median gives balanced halves. A random pivot or median of three makes the bad case very unlikely.
Pattern: Divide and conquer by partitioning
Recognition cues:
- Sort in place with no extra array
- Split elements by comparing each with a chosen value
- After one pass, one element is in its final position
Failure signals
- Sorting is very slow on data that is already sorted or nearly sorted.
- A stack overflow on a large input with a recursive quick sort.
- Records with equal keys come out in a different order than they went in.
Engineering examples
Standard library sorts
A general-purpose `sort()` has to be fast on arbitrary input and must not blow up on sorted data.
C++ `std::sort` uses introsort: quick sort for speed, a depth counter, and heap sort as the fallback so the worst case is still `O(n log n)`. Java sorts primitive arrays with dual-pivot quick sort.
Database and analytics engines sorting in memory
Sorting millions of rows in a query's working memory without allocating a second copy.
An in-place partition sort keeps the memory footprint flat and scans data in cache-friendly order.
When not to use
- You need a stable sort: Partition swaps do not preserve the order of equal elements. Use merge sort or Timsort.
- You cannot risk a slow worst case: Plain quick sort can hit `O(n^2)`. Use merge sort, heap sort or introsort when a hard `O(n log n)` bound matters.
- The data is a linked list or does not fit in memory: Partition relies on cheap random access to swap elements. Merge sort works with sequential access and on disk.
Common mistakes
- Recursing on the pivot too: Calling `quick_sort(lo, p)` instead of `quick_sort(lo, p - 1)` can leave a range the same size forever. The pivot is already placed; recurse on `[lo, p - 1]` and `[p + 1, hi]`.
- Last element as pivot on sorted input: On an already sorted array every partition peels off one element, giving `O(n^2)` time and an `n`-deep recursion that can overflow the stack. Randomize or use median of three.
- Many equal keys with a two-way partition: If everything equals the pivot, nothing counts as smaller and the split is always lopsided. Use a three-way partition when duplicates are likely.
- Assuming it is stable: Sorting records by one field and expecting ties to keep their earlier order will fail with quick sort. Use a stable sort, or add the original index as a tie-breaker.
Recall questions
- What does one partition step guarantee about the pivot?
- What is quick sort's time complexity on average and in the worst case?
- Which input makes quick sort slow when the last element is always the pivot, and why?
- How do you keep quick sort's stack depth at `O(log n)` even with bad splits?
- Why does a three-way partition help when many elements are equal?
- Quick sort versus merge sort: which is stable and which needs `O(n)` extra memory?
Understanding checks
Partition `[5, 1, 4, 2, 3]` with the last element (`3`) as the pivot, using the 'smaller than pivot goes to the left' rule. What is the array after the pivot is swapped into place, and at which index is it?
`[1, 2, 3, 5, 4]`, with the pivot `3` at index 2. Only `1` and `2` are smaller, so they are packed at the front. The pivot then swaps with the `4` that sits in the next slot.
The smaller elements are packed at the front, so the pivot's final index equals the number of elements smaller than it. Here that is 2.
This quick sort never finishes on some inputs. What is wrong?
It recurses on `[lo, p]` and `[p, hi]` instead of excluding the pivot, so a range can be passed down unchanged. Use `[lo, p - 1]` and `[p + 1, hi]`.
The pivot is already in its final place. Keeping it in a recursive range means the range may not shrink, so the recursion never reaches the stop condition.
You sort a list of 100,000 records by `last_name` with quick sort, and records with the same last name no longer appear in the order of their `first_name` from a previous sort. Why?
Quick sort is not stable. Partition swaps elements across long distances, so equal keys can swap their relative order.
Stability needs equal elements to keep their original order. Long-range swaps break that. Merge sort or a tie-breaker on the old position fixes it.
Questions & answers
Sort an array that only contains 0, 1 and 2 in one pass, in place.
Use a three-way partition (the Dutch national flag idea): keep a boundary for the zeros, a boundary for the twos, and a scanner. Swap each element into the right group as you scan.
Approach: This is quick sort's partition with pivot value 1 and three groups: smaller, equal, greater. It is the same trick described for equal keys.
Your quick sort overflows the stack on a large sorted input. Name two changes that fix it.
Pick the pivot randomly (or median of three) so sorted input no longer gives lopsided splits, and recurse only into the smaller side while looping on the larger side so the depth is at most `log2(n)`.
Approach: The first change removes the cause (bad pivots); the second caps the damage (stack depth) even if a split is bad.
An interviewer asks: why is quick sort often faster than merge sort even though merge sort has the better worst case?
Quick sort works in place on a contiguous array with sequential memory access and no allocation or copying, so its constant factor is smaller. The worst case is made very unlikely by a random or median-of-three pivot.
Approach: Compare the extra memory (`O(log n)` vs `O(n)`) and the memory access pattern, then address the worst case by naming the pivot fix.
Interesting facts
- Tony Hoare invented quick sort in 1959 as a visiting student in Moscow, where he needed to sort the words of a Russian-English dictionary for a machine translation project. He published it in 1961.
- Quick sort makes about 39% more comparisons than the theoretical minimum on random input (about `1.39 * n * log2(n)`), yet it usually beats sorts with fewer comparisons because of how kindly it treats the memory cache.
Continue learning
Previous: Merge Sort
Previous: Recursion tree
Next: Quicksort & partition
Next: Quickselect
Related: Merge Sort
Related: Quicksort & partition
Related: Quickselect
Related: Heap sort
Related: Non-comparison sorts