Problem. nums contains only 0, 1 and 2 (red, white, blue). Sort it in place so all 0s come first, then 1s,
then 2s, without using a library sort.
[2, 0, 2, 1, 1, 0] → [0, 0, 1, 1, 2, 2]
ML context. Sorting class labels or bucketed values is everywhere: grouping a batch by class for
balanced sampling, splitting data into train / validation / test buckets, and partitioning around a pivot (the core
of quicksort and of np.partition for top-k). When values come from a tiny known set, comparison sorting is
overkill.
1. Step 1: Clarify
| Question | Answer | Why it matters |
|---|---|---|
| Values? | Only 0, 1, 2 | Three known values: no comparisons needed |
| In place? | Yes, O(1) extra | Rules out building buckets |
| One pass required? | Ideally | Pushes counting → three pointers |
| Are these bare labels or records? | Bare labels | Stability doesn't matter (yet) |
| n? | Up to 300 here, millions in practice | Any O(n) method is fine |
2. Step 2: Brute force: a general sort
The simplest correct answer ignores the structure: sort.
def sort_colors_sort(nums):
nums.sort() # O(n log n), comparison-based
nums = [2, 0, 2, 1, 1, 0]
sort_colors_sort(nums)
assert nums == [0, 0, 1, 1, 2, 2]
print("built-in sort works: O(n log n)")
O(n log n). It's fast in practice, but it ignores the most important fact: there are only three values. Comparison sorting can't beat n log n in general, but we don't need comparisons at all.
3. Step 3: Optimise
Optimisation 1: count, then overwrite (two passes)
Count how many 0s, 1s and 2s there are, then write that many of each.
def sort_colors_count(nums):
counts = [0, 0, 0]
for x in nums: # pass 1: count
counts[x] += 1
i = 0
for value in range(3): # pass 2: overwrite
for _ in range(counts[value]):
nums[i] = value
i += 1
nums = [2, 0, 2, 1, 1, 0]
sort_colors_count(nums)
assert nums == [0, 0, 1, 1, 2, 2]
print("counting sort: O(n) time, O(1) extra (three counters), two passes")
O(n) time, O(1) space. This is counting sort, and for bare labels it's an excellent answer. The follow-up is usually: can you do it in one pass? (One pass matters when the data is streamed or each read is expensive.)
Optimisation 2: three pointers, one pass (the Dutch national flag)
First principles: keep an invariant. Split the array into four regions:
[0, low): all 0s[low, mid): all 1s[mid, high]: not yet examined(high, end]: all 2s
Look at nums[mid]:
- 0: swap it to
low; bothlowandmidmove right. - 1: it's already in the 1s region;
midmoves right. - 2: swap it to
high;highmoves left, butmidstays, because the value that came fromhighhasn't been examined yet.
Stop when mid > high: the unknown region is empty.
import random
def sort_colors(nums):
low, mid, high = 0, 0, len(nums) - 1
while mid <= high:
if nums[mid] == 0:
nums[low], nums[mid] = nums[mid], nums[low]
low += 1
mid += 1 # what came from low is a 1 (or mid == low): safe to skip
elif nums[mid] == 1:
mid += 1
else:
nums[mid], nums[high] = nums[high], nums[mid]
high -= 1 # mid stays: the swapped-in value is unexamined
for case in ([], [0], [2, 0, 1], [2, 0, 2, 1, 1, 0], [2, 2, 2], [1, 0]):
got = list(case)
sort_colors(got)
assert got == sorted(case), case
rng = random.Random(29)
for _ in range(1000):
case = [rng.randint(0, 2) for _ in range(rng.randint(0, 20))]
got = list(case)
sort_colors(got)
assert got == sorted(case)
print("three pointers: one pass, O(n) time, O(1) space, correct on 1,000 cases")
- Time: each step either moves
midright orhighleft, so at most n steps: O(n), one pass. - Space: O(1).
- Why
midcan advance after swapping a 0: everything betweenlowandmidis a 1 (already examined), so the value swapped back intomidis a 1, orlow == midand it's the 0 itself.
Quick check
Why doesn't mid advance after swapping a 2 to the high end?
Show the answer
B. The value swapped in from high hasn't been examined yet; it might be a 0 or a 2 that still needs moving — Everything in [mid, high] is unexamined, including the value that just arrived at mid.
4. When the constraints change
Change A: k distinct labels instead of 3
Three pointers don't generalise nicely beyond three groups. Counting sort does: O(n + k) time, O(k) space.
def sort_labels(labels, k):
counts = [0] * k
for x in labels:
counts[x] += 1
i = 0
for value in range(k):
for _ in range(counts[value]):
labels[i] = value
i += 1
labels = [3, 1, 4, 1, 0, 2, 4, 3]
sort_labels(labels, 5)
assert labels == [0, 1, 1, 2, 3, 3, 4, 4]
print("counting sort for k labels: O(n + k)")
Change B: sort records by label, keeping their order (stability)
Real data carries payloads: (label, sample_id). Overwriting with counts would lose the payloads, and the three-
pointer swaps scramble the order of equal labels (they're not stable). Use a stable counting sort: count,
compute each label's starting position (a prefix sum, lesson 1.2), then place records in their original order.
import random
def stable_sort_by_label(records, k):
counts = [0] * k
for label, _ in records:
counts[label] += 1
start, total = [0] * k, 0
for v in range(k): # prefix sums: where each label's block starts
start[v], total = total, total + counts[v]
out = [None] * len(records)
for rec in records: # original order → stable
out[start[rec[0]]] = rec
start[rec[0]] += 1
return out
batch = [(2, "a"), (0, "b"), (2, "c"), (1, "d"), (0, "e")]
assert stable_sort_by_label(batch, 3) == [(0, "b"), (0, "e"), (1, "d"), (2, "a"), (2, "c")]
rng = random.Random(30)
for _ in range(300):
recs = [(rng.randint(0, 3), i) for i in range(rng.randint(0, 15))]
assert stable_sort_by_label(recs, 4) == sorted(recs, key=lambda r: r[0]) # Python's sort is stable
print("stable counting sort: O(n + k) time, O(n) extra")
Change C: partition around a pivot (quicksort, top-k)
The three-pointer pass is a three-way partition: "less than pivot / equal / greater". Quicksort uses it so that
many equal keys don't degrade it to O(n²), and np.partition uses partitioning to find the top-k in O(n) on average
without fully sorting. That's module 6.
The full table
| If the constraint becomes… | Best approach | Time | Extra space | Stable? |
|---|---|---|---|---|
| Simplest code | Built-in sort | O(n log n) | O(n) | Yes |
| Values 0, 1, 2; two passes OK | Count, then overwrite | O(n) | O(1) | n/a (bare values) |
| One pass, in place | Three pointers | O(n) | O(1) | No |
| k distinct labels | Counting sort | O(n + k) | O(k) | n/a |
| Records with payloads, keep order | Stable counting sort | O(n + k) | O(n) | Yes |
| Partition around any pivot | Three-way partition | O(n) | O(1) | No |
Quick check
You must sort (label, sample) records by label and keep the original order of samples within each label. Which method fits?
Show the answer
A. Stable counting sort: count labels, prefix-sum the starting positions, then place records in their original order — Three-pointer swaps aren't stable, and count-and-overwrite loses the payloads. A stable counting sort keeps both.
5. Saying it out loud
"A general sort is O(n log n), but there are only three values, so counting is O(n) in two passes. For one pass, I'll keep three regions with low, mid and high: 0s before low, 1s between low and mid, 2s after high. A 0 swaps to low and both move; a 1 just moves mid; a 2 swaps to high and only high moves, since the new value is unexamined. O(n) time, O(1) space. If I had records and needed stability, I'd use a stable counting sort instead."
Check yourself
- Why can we beat O(n log n) here?
- State the four regions of the three-pointer invariant.
- Why does
midadvance after swapping a 0 but not after swapping a 2? - When is counting better than three pointers?
- Why isn't the three-pointer method stable, and what do you use when stability matters?
- Where else does three-way partitioning appear?
Answers
- There are only three known values, so we can count or partition without comparisons.
[0, low)zeros,[low, mid)ones,[mid, high]unexamined,(high, end]twos.- The value swapped from
lowis a 1 (already examined); the value swapped fromhighis unexamined. - With many distinct labels (k > 3), or when a second pass is fine and simpler code is preferred.
- Swaps move equal values past each other; use a stable counting sort with prefix-sum start positions.
- Quicksort with many equal keys, and selection / top-k (
np.partition).