Vibe Engines Learn
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.

SOLVE IT YOURSELF

Solve it: sort 0s, 1s and 2s in one pass

Three values, one pass, no counting and no sort call. Dijkstra’s three-pointer partition. Write it in Python or TypeScript, running for real in your browser.

YOUR TASK

Implement sort_colors(nums): given a list containing only 0, 1 and 2, return it sorted — in a single pass, using three pointers rather than counting occurrences.

HINTS — 5 IDEAS
  1. Keep three pointers: low (end of the 0s), mid (what you are looking at), high (start of the 2s).
  2. Loop while mid <= high. Everything before low is 0, everything after high is 2.
  3. See a 0: swap it down to low, then advance both low and mid.
  4. See a 1: it is already in the middle region — just advance mid.
  5. See a 2: swap it up to high and decrement high — but do not advance mid, because the value you just swapped in is unexamined. That single asymmetry is where almost everyone gets this wrong.
CPython · WebAssembly

Keep going

Algorithm

Quicksort →
Algorithm

Two Pointers →
Algorithm

Counting Sort →
Roadmap

The DSA Roadmap →
Finished this one? 0 / 99 Algorithms done

Explore the topic

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

Algorithms & DSA

More Algorithms

Explore more from Vibe Engines

Handbooks →
Roadmaps →
System Designs →
AI System Designs →
Labs →
Paper Breakdowns →
Challenges →