THE DUTCH NATIONAL FLAG three colors, one pass, three pointers — Dijkstra’s partition
When the keys take only three values — red, white, blue; or <, =, > a pivot — you can sort them in a single pass with three pointers. Dijkstra’s Dutch National Flag algorithm keeps a low boundary, a high boundary, and a scanner: a 0 swaps down to the low region, a 2 swaps up to the high region, a 1 is left in the middle. It is the 3-way partition that makes quicksort robust against duplicate keys (many-equal-elements is quicksort’s worst case), and the tidy answer to sorting a fixed small palette. Here [2,0,1,2,1,0] becomes [0,0,1,1,2,2] in one sweep.
THE TECHNIQUE low/mid/high pointers, one pass — 3-way partition of 0/1/2
The demo sorts [2,0,1,2,1,0] into [0,0,1,1,2,2] in a single three-pointer pass: live demo
HISTORY & CREDIT Edsger Dijkstra · the Dutch flag
“Sorting even three values takes O(n log n).” — three pointers sort a 3-value array in one linear pass. cited
the pointers · low, mid, high — a 0 goes to low, a 2 to high, a 1 stays. the pass · one linear sweep; each element placed once — O(n), O(1) space. the use · the 3-way partition that tames quicksort’s duplicate-key worst case; Dijkstra.
Three colors sorted by three pointers in one sweep — the partition that handles ties. resource
RECOMMEND FOR I-13 the one-pass flag, on the compiler
On the canonical compiler, [2,0,1,2,1,0] sorts to [0,0,1,1,2,2] in one three-pointer pass:
$ i13 run or_dutchflag.i13 # 3-way partition
RUN OK · 416 step(s) · peak stack 7 · call depth 7
is_sorted = 1 -- [0,0,1,1,2,2]
Recommend as a NULL — a one-pass 3-way partition, i.e. resource. The Dutch flag sorts a 3-valued array in O(n) with O(1) space — a resource-optimal special case (B40), and the duplicate-robust partition inside good quicksorts. No new invariant. NULL — Dijkstra’s tidy sweep.