Quicksort & Partitioning
How quicksort picks a pivot, splits the array in a single pass, and recurses — plus why a bad pivot turns O(n log n) into O(n²), and how real libraries dodge it.
What you'll learn
- How one partition pass places the pivot in its final home and splits the rest around it
- Why quicksort averages O(n log n) but collapses to O(n²) on sorted input with a naive pivot
- The three practical pivot strategies — last, random, median-of-three — and when each matters
- Why quicksort (as introsort) is the default in-memory sort despite that O(n²) worst case
Before you start
Quicksort rests on one disarmingly simple move. Pick an element to be the pivot, rearrange the array so that everything smaller sits to its left and everything larger to its right, and then do the same to each side. That rearrangement is called a partition, and the lovely thing about it is this: once it finishes, the pivot is sitting in its final, sorted position forever. You never touch it again.
The idea
Imagine your cards laid out, and you point at one — say the last — as the pivot. You slide every smaller card to its left and every larger card to its right, then drop the pivot into the gap between them. Now you have three groups: a left group (unsorted, but all smaller than the pivot), the pivot (done), and a right group (unsorted, but all larger). Run the very same procedure on the left group, then on the right, and the deck sorts itself through a cascade of partitions.
The key fact is that one partition costs O(n) and permanently places one element. If the pivot keeps landing near the middle, each round halves the work — and halving log n times, with O(n) per level, gives O(n log n) overall.
Watching one partition
The common scheme is Lomuto partition: take the last element as pivot, sweep left to right, and keep a boundary just past the “small” zone. Each time you meet something ≤ the pivot, you swap it into the small zone and push the boundary forward. At the end, you drop the pivot right after the small zone. Let us partition [6, 2, 8, 1, 4] with pivot 4:
[6, 2, 8, 1, 4] pivot = 4
6 > 4 → leave it
2 ≤ 4 → swap into the small zone → [2, 6, 8, 1, 4]
8 > 4 → leave it
1 ≤ 4 → swap into the small zone → [2, 1, 8, 6, 4]
drop the pivot after the small zone → [2, 1, 4, 6, 8]The code
def partition(arr, lo, hi):
pivot = arr[hi] # last element is the pivot
i = lo - 1 # boundary of the "small" zone
for j in range(lo, hi):
if arr[j] <= pivot:
i += 1
arr[i], arr[j] = arr[j], arr[i]
arr[i + 1], arr[hi] = arr[hi], arr[i + 1] # drop pivot after the small zone
return i + 1 # the pivot's final index
def quicksort(arr, lo=0, hi=None):
if hi is None:
hi = len(arr) - 1
if lo < hi:
p = partition(arr, lo, hi)
quicksort(arr, lo, p - 1) # sort the smaller-than-pivot side
quicksort(arr, p + 1, hi) # sort the larger-than-pivot side
return arr
print(quicksort([7, 2, 9, 4, 1, 8, 3, 6, 5, 10]))[1, 2, 3, 4, 5, 6, 7, 8, 9, 10]The cost, and the trap
| Case | Time | Space |
|---|---|---|
| Average / best | O(n log n) | O(log n) stack |
| Worst | O(n²) | O(n) stack |
Quicksort sorts in place — the rearranging all happens inside the original array, with only the recursion stack as overhead. That keeps the elements being compared close together in memory, which the CPU cache loves; it is the main reason quicksort outruns merge sort on random data. It is not stable, though — swaps can reorder equal elements.
The average case is forgiving: a pivot does not have to be the exact median, it just has to avoid the extremes, which a typical element does. But there is a trap.
Why it dominates anyway
Merge sort also guarantees O(n log n), but it pays O(n) extra memory for the merge buffer. Quicksort’s in-place partitioning means better cache locality, and that constant-factor edge is enough that quicksort — wrapped in introsort’s safeguards — wins most in-memory benchmarks on random data. You see the pattern across standard libraries:
- C++
std::sort— introsort (quicksort + heapsort fallback + insertion sort for tiny slices). - Java
Arrays.sortfor primitives — dual-pivot quicksort. - Rust
sort_unstable— pattern-defeating quicksort (pdqsort). - NumPy
sort(kind="quicksort")— an introsort variant.
Pure quicksort is fast but brittle; production sorts keep its speed and bolt on the guarantees.
Practice
Quick check
Practice this in an interview
All questionsEven after rotation, one of the two halves around mid is always fully sorted. Check which half is sorted, then decide whether the target falls inside it. If yes, narrow to that half; if no, search the other. This keeps binary search's O(log n) guarantee.
Use a slow pointer that tracks where the next unique value should be written, and a fast pointer that scans forward. Whenever the fast pointer finds a value different from the current unique one, copy it to the slow pointer's position and advance both. One pass, O(1) extra space.
Partitioning divides a large table into smaller physical segments (partitions) based on a column value, so the planner can skip irrelevant partitions entirely — a technique called partition pruning. It improves performance for queries that filter on the partition key, and it simplifies bulk data management tasks like dropping old data by dropping a partition instead of issuing a slow DELETE.
Binary search halves the search space each iteration to find a target in O(log n). The tricky part is not the idea but the boundary conditions: closed vs. half-open intervals, how to update lo/hi, and when to use lo < hi vs. lo <= hi. One clean template eliminates all the classic bugs.