VFlash: Fast, Accurate Visual Planning via Flash Primitive Decoding
u_Unrolled
DSA for AI/ML · Module 01: Arrays and strings

Lesson 1.14 of 16 in this moduleFree

Sort Colors

Sort an array of 0s, 1s and 2s in place: from a general sort, to counting in two passes, to the one-pass three-pointer partition with its invariant. Then k labels, stability for records, and partitioning in quicksort.

about 10 min 5 Python examples 2 quick checks

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.

text
[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.

python
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.

python
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; both low and mid move right.
  • 1: it's already in the 1s region; mid moves right.
  • 2: swap it to high; high moves left, but mid stays, because the value that came from high hasn't been examined yet.

Stop when mid > high: the unknown region is empty.

seven frames over [2, 0, 2, 1, 1, 0] showing low, mid and high; zeros collect on the left, twos on the right, and the scan ends when mid passes high with [0, 0, 1, 1, 2, 2].
Diagram— seven frames over [2, 0, 2, 1, 1, 0] showing low, mid and high; zeros collect on the left, twos on the right, and the scan ends when mid passes high with [0, 0, 1, 1, 2, 2].
python
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 mid right or high left, so at most n steps: O(n), one pass.
  • Space: O(1).
  • Why mid can advance after swapping a 0: everything between low and mid is a 1 (already examined), so the value swapped back into mid is a 1, or low == mid and it's the 0 itself.

Quick check

Why doesn't mid advance after swapping a 2 to the high end?

  1. To save a step
  2. The value swapped in from high hasn't been examined yet; it might be a 0 or a 2 that still needs moving
  3. Because 2s are already sorted
  4. It should advance; this is a bug
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

a decision map: a built-in sort for simplicity, counting and overwriting for three values, three pointers for one pass in place, counting sort for k labels, and a stable counting sort when records must keep their order.
Diagram— a decision map: a built-in sort for simplicity, counting and overwriting for three values, three pointers for one pass in place, counting sort for k labels, and a stable counting sort when records must keep their order.

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.

python
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.

python
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?

  1. Stable counting sort: count labels, prefix-sum the starting positions, then place records in their original order
  2. Three pointers, since it's one pass
  3. Count and overwrite, since it's O(n)
  4. Any method works
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

  1. Why can we beat O(n log n) here?
  2. State the four regions of the three-pointer invariant.
  3. Why does mid advance after swapping a 0 but not after swapping a 2?
  4. When is counting better than three pointers?
  5. Why isn't the three-pointer method stable, and what do you use when stability matters?
  6. Where else does three-way partitioning appear?
Answers
  1. There are only three known values, so we can count or partition without comparisons.
  2. [0, low) zeros, [low, mid) ones, [mid, high] unexamined, (high, end] twos.
  3. The value swapped from low is a 1 (already examined); the value swapped from high is unexamined.
  4. With many distinct labels (k > 3), or when a second pass is fine and simpler code is preferred.
  5. Swaps move equal values past each other; use a stable counting sort with prefix-sum start positions.
  6. Quicksort with many equal keys, and selection / top-k (np.partition).