Lesson 18
Quick Sort & Partitioning
Pick a pivot, split around it, recurse — the fastest sort in practice.
01Why it matters & the intuition
Quick sort is in-place and cache-friendly, which is why it beats merge sort on real hardware. Its partition step is also the heart of quickselect (k-th smallest in O(n) average).
Think of it like…
Line up a class by height: pick one student as the pivot. Everyone shorter moves left, everyone taller moves right. The pivot is now exactly where they belong — repeat for each side.
02See it move
Press play, then step through slowly. Change the input and predict the next frame before you click.
- comparing / current
- moving / removing
- done / found / visited
- pivot / min / root
03Key ideas
Partition (Lomuto)
Choose the last element as pivot. Sweep left to right keeping a boundary i; swap anything smaller than the pivot behind the boundary. Finally swap the pivot to i.
Pivot choice
A bad pivot (always the min or max) makes one side empty and time O(n²). Random or median-of-three pivots make that vanishingly rare.
In place
Only O(log n) stack space on average — no merge buffers.
Three-way partition
Splitting into < pivot, = pivot, > pivot handles many duplicates gracefully (Dutch national flag).
04Build it from scratch
A clean reference implementation. Read it line by line — then close it and write your own in the lab below.
function quickSort(a: number[], lo = 0, hi = a.length - 1): number[] {
if (lo >= hi) return a;
const p = partition(a, lo, hi);
quickSort(a, lo, p - 1);
quickSort(a, p + 1, hi);
return a;
}
function partition(a: number[], lo: number, hi: number): number {
// Random pivot defends against sorted-input worst case.
const r = lo + Math.floor(Math.random() * (hi - lo + 1));
[a[r], a[hi]] = [a[hi], a[r]];
const pivot = a[hi];
let i = lo;
for (let j = lo; j < hi; j++) {
if (a[j] < pivot) { [a[i], a[j]] = [a[j], a[i]]; i++; }
}
[a[i], a[hi]] = [a[hi], a[i]];
return i;
}05Complexity
| Operation | Time | Space |
|---|---|---|
| Average time | O(n log n) | — |
| Worst time (bad pivots) | O(n²) | — |
| Space | — | O(log n) stack |
| Stable | no | — |
06Check your understanding
07Code lab
Write Python(or switch to JavaScript) and run it against real test cases. Python runs inside your browser — nothing is uploaded — and a C++ reference solution is under “Solution”.
Sort colours (three-way partition)
Write sort_colors(nums) where nums contains only 0, 1 and 2. Sort it in place in one pass with O(1) space and return it. No .sort().