Quick Sort
Task: Sort this array in ascending order
Why we need Quick Sort
Analogy
- A teacher wants forty students standing in a line by height, shortest to tallest.
- Instead of comparing every pair, she picks one student, Ashu, and says: everyone shorter than Ashu stand on his left, everyone taller stand on his right.
- Nobody is sorted yet. But Ashu is now standing in exactly the right place, and he will never move again.
- And one hard problem has become two smaller ones: sort the left group, sort the right group. Each group picks its own student and does the same thing.
What is quick sort?
Definition
Quick sort picks one value as the pivot, moves everything smaller to its left and everything bigger to its right, and then sorts each side the same way.
That single rearranging pass is called partitioning, and it is where all the work happens.
Sorting a whole array is hard. Putting one value in its final place is easy, and quick sort is built entirely out of doing the easy thing over and over.
The partition, which is the whole algorithm
Take 7 2 1 6 8 5 3 4 and use the last value, 4, as the pivot.
Walk the row once from the left. Keep a low region growing behind you, holding everything found so far that is at or below the pivot. Anything bigger is left where it is. Anything smaller is swapped into the low region.
When the walk is over, swap the pivot into the gap just past the low region. Everything on its left is smaller and everything on its right is bigger, so 4 is now exactly where it belongs in the finished array.
One pass. Every value looked at once. A partition costs n steps.
What that one pass actually buys
Two things, and the second is the one people miss.
One value is placed for good. The pivot is home. Nothing later in the algorithm will move it.
The two sides never need to meet again. Every value on the left is smaller than every value on the right, so no value on one side will ever be compared with a value on the other. The problem has not merely got smaller. It has split into two problems that have nothing to do with each other.
Note
This is why quick sort has no combining step. Once both sides are sorted, the array is sorted, because the sides were already in the right order relative to each other. There is nothing to merge and nothing to stitch back together.
Try it
Try it yourself
One sweep, and one value is finished for good
Press partition and watch what happens: a lot of values shuffle around, and exactly one turns green. That is the deal quick sort makes, and it is the same deal every time.
Watch the underline too. It marks the stretch still being worked on, and it shrinks after every partition, because everything outside it has become somebody else's problem.
Why it sorts, in three lines
Every value becomes a pivot exactly once. A value that becomes a pivot is put in its final position. So when there are no pivots left to pick, every value is in its final position.
That is the whole correctness argument, and there is no arithmetic in it.
Why it is usually fast, and when it is not
A partition costs n. So the only question left is how many levels of partitioning there are, and that depends entirely on where the pivots land.
A pivot near the middle cuts the work roughly in half each time: n, then n/2, then n/4, down to one. That is log2 n levels, so n work on each of log n levels gives O(n log n).
A pivot that happens to be the largest value peels off one at a time. The array shrinks by one per level instead of halving, which is n levels, and n work on each of n levels is O(n2).
Watch out
With the last value as the pivot, an already sorted array is the worst case. The pivot is the largest value every single time, so every split is as lopsided as it can be.
This catches people out, because sorted data is the most natural thing to test with. The code is not broken. The pivot rule is.
The fix is to break the link between the order of the input and the choice of pivot:
- Pick the pivot at random. Then no particular input is reliably bad.
- Median of three. Take the median of the first, middle and last values. Cheap, and it kills the sorted-array case.
The worst case never technically goes away. It just stops being something you will meet.
In code
def quick_sort(arr, lo=0, hi=None): if hi is None: hi = len(arr) - 1 if lo < hi: p = partition(arr, lo, hi) quick_sort(arr, lo, p - 1) quick_sort(arr, p + 1, hi) return arr def partition(arr, lo, hi): pivot = arr[hi] i = lo for j in range(lo, hi): if arr[j] <= pivot: arr[i], arr[j] = arr[j], arr[i] i += 1 arr[i], arr[hi] = arr[hi], arr[i] return iThe highlighted line is the one that does the placing. Everything above it only decides where the gap is.
Watch out
Notice p - 1 and p + 1 in the two recursive calls. The pivot is excluded from both, because it is already finished. Passing p itself into a recursive call is the single most common cause of quick sort never terminating.
What it costs
| Case | Time | Space | Why |
|---|---|---|---|
| Best | O(n log n) | O(log n) | Pivots land near the middle, so the array halves each level. |
| Average | O(n log n) | O(log n) | Random pivots are near the middle often enough. |
| Worst | O(n2) | O(n) | Every pivot is the largest or smallest value left. |
The space is the recursion stack and nothing else. Quick sort sorts in place: there is no second array, and nothing is ever copied back.
Quick sort against merge sort
The clearest way to see the difference is to ask where each one does its work.
| Quick sort | Merge sort | |
|---|---|---|
| Splitting | Hard: partition around a pivot | Easy: cut in the middle |
| Combining | Nothing to do | Hard: merge two sorted runs |
| Worst case | O(n2) | O(n log n) |
| Extra memory | O(log n) | O(n) |
| Stable | No | Yes |
Merge sort puts off all its work until the way back up. Quick sort does all of its work on the way down. One of them has to be the hard part, and each algorithm picks a different one.
Note
Quick sort is usually the faster of the two on a normal array in memory, even though its worst case is worse. It sorts in place, so there is no second array to allocate, and it reads memory straight through, which processor caches are very good at. Merge sort wins when you need the guarantee, when you need stability, or when the data does not fit in memory.
Two things that trip it up
It is not stable. Partitioning swaps values that were far apart, so two equal values can come out in the opposite order to the one they went in. Sort employees by name and then by department, and quick sort will scramble the names inside each department. Merge sort will not.
Duplicates. If a lot of values are equal, they all pile onto one side of the pivot and the splits go lopsided, which is the slow case again. The fix is to partition into three regions rather than two: less than, equal to, and greater than. The equal region is already finished, so only the outer two are sorted further. On an array where every value is the same, that turns O(n2) into O(n).
Where you have seen it
- The sort in most standard libraries. C's
qsort, and the sort behind Java'sArrays.sortfor primitives. - C++
std::sort, which runs quick sort but switches to heap sort if the recursion gets suspiciously deep, so the bad case cannot actually happen. - Finding the k-th smallest value without sorting. Partition, see which side k falls on, and recurse into only that side. That is quickselect, and it averages O(n).
Quick recap
- Pick a pivot, and partition the array around it in one pass
- That pass places the pivot for good and splits the rest into two independent halves
- Sort each half the same way, and stop: there is nothing to combine
- Levels are what cost you, and the pivot decides how many there are
Key takeaway
Sorting a whole array is hard. Placing one value is easy. Quick sort only ever does the easy thing, and lets that add up to the hard one.