Work one through by hand
Sort [7, 2, 9, 4, 1, 8] using the last element, 8, as pivot.
less than 8: [7, 2, 4, 1] | pivot: 8 | greater: [9]
8 is now final at index 4. Recurse left on [7, 2, 4, 1] with pivot 1:
less: [] | pivot: 1 | greater: [7, 2, 4]
Then [7, 2, 4] with pivot 4 gives [2] | 4 | [7], and everything is placed. Note the second partition was badly unbalanced — 0 elements against 3 — which is exactly the behaviour that causes the worst case.
Best case, worst case, and why the average holds
When the pivot lands near the median, each partition halves the array, giving log n levels of O(n) partitioning work: O(n log n).
When the pivot is consistently the smallest or largest element, one side gets n−1 elements and the other gets none. That gives n levels of O(n) work: O(n²). With a fixed first- or last-element pivot this is triggered by already-sorted input — the most common real-world case, which is why naive quick sort is dangerous.
The saving grace is that the average is robustly O(n log n). Even a split as lopsided as 90/10 at every level still gives logarithmic depth, just with a larger base. You need consistently near-worst pivots to reach quadratic, and randomising the pivot makes that vanishingly unlikely for any fixed input.
Partition, then recurse
Quick sort picks an element as the pivot, rearranges the array so everything smaller sits left of it and everything larger sits right, and then sorts each side recursively.
After one partition the pivot is in its final position, and the two sides are independent problems.
Sorting [38, 27, 43, 3, 9, 82, 10] with 10 as the pivot:
| Step | Result |
|---|
| Partition on 10 | [3, 9] 10 [38, 27, 43, 82] |
| Sort left | [3, 9] |
| Sort right on pivot 43 | [27, 38] 43 [82] |
| Combined | [3, 9, 10, 27, 38, 43, 82] |
No merge step is needed, which is the structural difference from merge sort: quick sort does its work before recursing, merge sort after.
Why the pivot decides everything
A good pivot splits the array roughly in half, giving log n levels of recursion with O(n) work each — O(n log n).
A bad pivot splits off one element, giving n levels — O(n²).
| Pivot quality | Recursion depth | Complexity |
|---|
| Median every time | log n | O(n log n) |
| Random | ~1.4 log n expected | O(n log n) expected |
| Always the smallest | n | O(n²) |
The classic trap: choosing the first element as the pivot makes already-sorted input the worst case. Sorted input is extremely common in practice, so this is not a theoretical concern — it is the most likely input in many systems.
Two standard fixes:
Randomised pivot. Choose uniformly at random. The worst case still exists and requires adversarial luck; expected time is O(n log n).
Median-of-three. Take the median of the first, middle and last elements. Cheap, deterministic, and it handles sorted and reverse-sorted input well.
Production implementations go further: introsort starts with quick sort, tracks recursion depth, and switches to heap sort if it exceeds 2 log n — guaranteeing O(n log n) while keeping quick sort's speed in the common case. That is what C++'s std::sort does.
Lomuto partitioning
The simpler of the two classic schemes, and the one worth memorising:
def quicksort(arr, lo=0, hi=None):
if hi is None:
hi = len(arr) - 1
if lo >= hi:
return
p = partition(arr, lo, hi)
quicksort(arr, lo, p - 1)
quicksort(arr, p + 1, hi)
def partition(arr, lo, hi):
import random
random.seed() # randomised pivot
r = random.randint(lo, hi)
arr[r], arr[hi] = arr[hi], arr[r] # move pivot to the end
pivot = arr[hi]
i = lo # boundary of the "smaller" region
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] # pivot into place
return i
The invariant is what makes it work: everything left of i is smaller than the pivot, everything from i to j is larger, and j scans forward. When the loop ends, swapping the pivot into position i puts it exactly where it belongs.
Note the in-place property: no auxiliary array, only swaps. That is quick sort's main advantage over merge sort.
Exploration guide
- Watch a pivot settle permanently. Set Array Size to 15 and press Next Step through one partition. When it completes, the pivot is in its final position and is never moved again — unlike merge sort, elements finish one at a time.
- Find a bad split. Press Randomize Array and Auto-Run a few times, watching the partition sizes. Occasionally one side gets almost everything; that single unbalanced level is a small dose of the worst case.
- Compare the recursion shape with merge sort. Merge sort’s tree is always perfectly balanced because it splits by position. Quick sort’s depends entirely on the values, so the tree is lopsided and different on every run.
- Scale it. Run a full sort at Array Size 5 and then 25. The comparison count grows roughly like n log n, noticeably slower than the n² growth of insertion sort at the same sizes.
Why it beats merge sort in practice
Both are O(n log n) on average, yet quick sort is usually faster on arrays. Three reasons:
- No auxiliary array. Partitioning is in-place, needing only O(log n) stack space for the recursion. Merge sort needs an O(n) buffer, and allocating and touching it costs real time.
- Cache behaviour. Partitioning sweeps two pointers inward through contiguous memory, which is close to the ideal access pattern for a CPU prefetcher.
- Smaller constant factor. The inner loop is a comparison and a conditional swap, with no writes to a second array and no copy-back.
Production implementations defend the worst case rather than accepting it: median-of-three or random pivot selection makes sorted input harmless, and introsort — the C++ standard library’s sort — counts recursion depth and switches to heap sort if it exceeds 2 log n, converting the quadratic worst case into a guaranteed O(n log n).
Common mistakes
- Always taking the first or last element as pivot. This makes already-sorted input the worst case, which is the input you are most likely to receive. Use median-of-three or a random pivot.
- Mishandling duplicates. An array of all-equal elements sends every element to one side under naive partitioning, giving O(n²). Three-way (Dutch national flag) partitioning splits into less / equal / greater and handles it in linear time.
- Recursing on the larger side first. Recursing into the smaller partition and looping on the larger caps stack depth at O(log n). Doing it the other way risks stack overflow on adversarial input.
- Expecting stability. Quick sort is not stable — partitioning swaps distant elements and reorders equal keys. If you need stability, use merge sort.
The short version
Quick sort partitions around a pivot, placing that pivot permanently and recursing on both sides with no combine step. In-place, cache-friendly and with a small constant factor, it is the fastest general-purpose array sort in practice — provided the pivot is chosen so that sorted input is not the worst case. Its O(n²) ceiling is real but avoidable, and every serious implementation avoids it by randomising the pivot or by falling back to heap sort when the recursion runs too deep.
Quick sort against merge sort
| | Quick sort | Merge sort |
|---|
| Average time | O(n log n) | O(n log n) |
| Worst time | O(n²) | O(n log n) |
| Extra space | O(log n) stack | O(n) |
| Stable | No | Yes |
| Cache behaviour | Excellent | Good |
| Typical speed | Faster | Slower constant factor |
Quick sort wins in practice on arrays despite the worse guarantee, for two reasons. It sorts in place, so no large auxiliary allocation. And its memory access pattern is sequential within each partition, which suits CPU caches well.
Merge sort wins where its guarantees matter: stability (equal elements keep their relative order, which matters when sorting by one key after another), a hard O(n log n) bound, and external sorting of data too large for memory.
Python's sorted uses Timsort, a merge sort variant that detects existing sorted runs and merges them, giving O(n) on nearly-sorted input — and it is stable, which Python guarantees.
Duplicates, and three-way partitioning
Plain Lomuto partitioning handles many equal elements badly. If every element is identical, each partition splits off one element and the algorithm degrades to O(n²).
Three-way partitioning (the Dutch national flag arrangement) splits into three regions — less than, equal to, and greater than the pivot — and recurses only on the outer two. All the equal elements are placed in one pass.
That turns an array of many duplicates from the worst case into the best case: sorting n identical elements becomes O(n).
It is worth knowing because arrays with few distinct values are common in real data — status flags, categories, boolean columns — and this is the variant that handles them.
Quickselect: the same idea for the k-th element
Partitioning tells you the pivot's final position. If that position is k, the pivot is the k-th smallest element and no further work is needed. If not, recurse into only the side containing k.
Quickselect is that algorithm, and it finds the k-th smallest element in O(n) expected time rather than the O(n log n) of sorting.
Uses: finding a median, the top k items, or a percentile without sorting the whole array. Python's heapq.nlargest uses a heap instead, which is better when k is small; quickselect wins for a median.
The pivot is the algorithm
Quick sort's average case and its worst case are the same code with a different pivot rule. That makes it a good thing to measure rather than describe: the same input, four pivot strategies, and the comparison counts tell you which choices are safe and which are a denial-of-service waiting to happen.
Questions people ask
Why use quick sort if the worst case is O(n²)? With randomised or median-of-three pivots the worst case is practically unreachable, and its in-place operation and cache behaviour make it faster than merge sort in the average case.
Is quick sort stable? No — partitioning swaps distant elements. Use merge sort or Timsort if stability matters.
How much extra memory does it use? O(log n) for the recursion stack, and O(n) in the degenerate case. Tail-call elimination on the larger side bounds it.
What does Python use? Timsort, which is a stable merge sort exploiting existing runs. list.sort() and sorted() both use it.
When is merge sort better? Linked lists (no random access needed), external sorting, and whenever stability or a hard worst-case bound is required.
What is introsort? Quick sort that switches to heap sort when recursion gets too deep, giving a guaranteed O(n log n) with quick sort's typical speed.
Recap in one screen
- Partition around a pivot so the pivot lands in its final position, then recurse on each side.
- The pivot choice decides everything: randomised or median-of-three, never the first element.
- In-place with good cache behaviour, which is why it beats merge sort in practice despite the O(n²) worst case.
- Not stable; use Timsort or merge sort when equal elements must keep their order.
- Three-way partitioning handles many duplicates, and quickselect finds the k-th element in O(n).