Algorithms · Three-Way Partition

The Dutch National Flag.

A scrambled row of red, white and blue — 0s, 1s and 2s. Sort them into three clean bands. The obvious fix counts each color and rewrites; the beautiful fix uses three pointers in a single in-place sweep, and never touches an element twice unnecessarily. Named for the flag it builds, it’s also the partition that makes quicksort fast when values repeat.

O(n) time · O(1) space · in-place · one pass
low

Everything left of low is a settled 0 (red).

mid

The scanner. Between low and mid sits settled 1s (white).

high

Everything right of high is a settled 2 (blue).

unexplored

The shrinking gap from mid to high — the only region still in question.

sort_colors.js — one pass, three pointers
0 red 1 white 2 blue
Ready
A scrambled flag of 0s, 1s and 2s. Three pointers — low, mid, high — will sort it in one pass. Press Step: we look at arr[mid] and act on its color.
0
low
0
mid
8
high

How it works

The array is always four regions: settled 0s (before low), settled 1s (from low to mid), an unexplored gap (mid to high), and settled 2s (after high). Every step shrinks the gap by examining arr[mid] and doing one of three things — the whole algorithm is a three-way switch.

0

Saw a 0 (red)

Swap it down to low, then advance both low and mid. The value coming back is already-examined, so mid can move on.

1

Saw a 1 (white)

It’s already in the right band. Just advance mid.

2

Saw a 2 (blue)

Swap it up to high, then shrink high — but don’t move mid: the value swapped back is from the unexplored gap and must be examined next.

Stop when mid passes high

The gap is empty; the flag is sorted. One pass, no counting, no extra array.

Time
O(n)
Space
O(1)
Passes
1
Stable?
No (it swaps)

The code

# sort an array of 0s, 1s, 2s in place, one pass def sort_colors(a): low, mid, high = 0, 0, len(a) - 1 while mid <= high: if a[mid] == 0: a[low], a[mid] = a[mid], a[low] low += 1; mid += 1 elif a[mid] == 1: mid += 1 else: # a[mid] == 2 a[mid], a[high] = a[high], a[mid] high -= 1 # mid stays! return a

The one asymmetry — mid advances on a 0 but not on a 2 — is the whole subtlety, and the most common bug. A 0 swaps back a value we already sorted; a 2 swaps back a value we haven’t seen. Get that right and the rest is mechanical.

Quick check

1. When arr[mid] is a 2, why doesn’t mid advance after the swap?

2. Why prefer this over counting the 0s, 1s and 2s?

FAQ

What is the Dutch national flag problem?

Sorting an array of three distinct values into three contiguous bands — like the red/white/blue of the Dutch flag — in place, in one pass. Named and popularized by Dijkstra.

Does it generalize beyond three values?

The exact three-pointer form is for three groups, but the idea — partition around a pivot value into less-than / equal / greater-than — is the general three-way partition used inside quicksort to handle duplicate keys efficiently.

Is it stable?

No. It swaps elements across the array, so equal elements can change relative order. If you need stability, count-and-rebuild or a stable sort is the trade-off.

Where does it show up in practice?

The classic "sort colors" interview question, and as the partition scheme (three-way / fat-partition quicksort) that keeps quicksort near O(n log n) on inputs with many repeated values.

Keep going

Finished this one? 0 / 62 Algorithms done

Explore the topic

See this alongside everything else on the same subject — handbooks, system designs, challenges and tools, in one place.

More Algorithms