Dutch National Flag: Three-Way Partitioning in One Pass

What it is and the problem it solves

Imagine an array of characters like ['B','R','W','R','B','W','R'] where R, W, B are the only three values, and you must group all R's, then all W's, then all B's. The naive fixes are unsatisfying: sorting is O(n log n) overkill for three keys; counting each value and rewriting the array takes two passes over the data.

Dijkstra's insight was that you can do it in one pass with three moving pointers, mutating the array as you go. He framed it with the Dutch flag's colors to make the invariant vivid.

The real payoff is not sorting balls — it is three-way partitioning around a pivot inside quicksort. Classic two-way partitioning splits into < pivot and ≥ pivot. But when the input has many equal keys (say, an array of all zeros, or a column with low cardinality), those equal elements get shuffled repeatedly and quicksort degrades toward O(n^2). The Dutch National Flag scheme carves out a third region — elements equal to the pivot — which are then final and excluded from recursion.

How it works: three pointers, four regions

The algorithm maintains three indices and, at every step, the array is conceptually split into four regions:

• [0, low) — all less than the pivot (the 'red' band)
• [low, mid) — all equal to the pivot (the 'white' band, finalized)
• [mid, high] — unknown, not yet examined
• (high, n-1] — all greater than the pivot (the 'blue' band)

You scan with mid, shrinking the unknown region from both ends until it is empty (mid > high):

low = 0; mid = 0; high = n - 1
while mid <= high:
    if a[mid] < pivot:
        swap(a[low], a[mid]); low++; mid++
    elif a[mid] > pivot:
        swap(a[mid], a[high]); high--   # mid NOT advanced
    else:                # a[mid] == pivot
        mid++

The subtle rule: after swapping with high, you do not advance mid, because the value pulled in from the right is unexamined. After a swap with low you can advance both, since the element coming from low was already known to equal the pivot.

Complexity and a worked step trace

Time: O(n). Each iteration either advances mid or retreats high, and the loop ends when they cross — so the body runs at most n times. Space: O(1) auxiliary (three index variables, in-place swaps). It is not stable: swapping across the array reorders equal-key-distinct-payload elements.

Trace on [2,0,2,1,1,0] with pivot 1 (0=<, 1==, 2=>), starting low=0, mid=0, high=5:

[2,0,2,1,1,0]  a[mid]=2>piv → swap(mid,high), high=4
[0,0,2,1,1,2]  a[mid]=0<piv → swap(low,mid), low=1,mid=1
[0,0,2,1,1,2]  a[mid]=0<piv → swap(low,mid), low=2,mid=2
[0,0,2,1,1,2]  a[mid]=2>piv → swap(mid,high), high=3
[0,0,1,1,2,2]  a[mid]=1==piv → mid=3
[0,0,1,1,2,2]  a[mid]=1==piv → mid=4
               mid(4) > high(3) → STOP
result: [0,0,1,1,2,2]   ✓

Six elements, six iterations, sorted in place with a handful of swaps.

Where it's used in real systems

The most important application is 3-way quicksort (Bentley & McIlroy's 1993 refinement, and Sedgewick's teaching variant). By finalizing the equal-to-pivot band, sorting an array with only k distinct keys runs in O(n log k) rather than O(n log n) — and an array of all-equal keys is sorted in linear time. This is why production sorts guard against low-cardinality inputs:

• Standard libraries: introsort-style sorts and many language runtimes special-case equal keys; Java's dual-pivot quicksort and various std::sort implementations use multi-way partitioning ideas to stay fast on duplicates.
• Databases & analytics: sorting or grouping columns with low cardinality (booleans, enums, status flags) benefits directly from collapsing equal runs.
• Selection (quickselect): the same three-way split lets median-finding skip the equal band, improving worst-case behavior on repeated values.
• Interview canon: LeetCode 75 'Sort Colors' is this problem verbatim, making it one of the most-taught partitioning routines in industry.

Comparison to the alternatives

The natural rivals are counting sort and two-way (Lomuto/Hoare) partitioning.

• vs. counting sort: Counting sort also handles three values in linear time, but it needs two passes (count, then place) and assumes a known, tiny key range. Dutch National Flag is a genuine single pass and generalizes to a pivot comparison (<, ==, >), so it works when the three 'colors' are defined relative to an arbitrary pivot, not fixed symbols.
• vs. Lomuto/Hoare: Two-way partitioning produces only two regions and no equal band. On an input of many duplicates, equal elements ping-pong across the pivot and quicksort recurses on nearly-full subarrays — the classic path to O(n^2). The Dutch scheme's third region is precisely the fix.

The tradeoff: three-way partitioning does slightly more bookkeeping and swaps per element than a tight two-way loop, so on inputs that are already all distinct, a well-tuned two-way partition can edge it out. The win only materializes when duplicates are present — which, in real data, they very often are.

Pitfalls, failure modes, and significance

The most common bug is advancing mid after the a[mid] > pivot swap. The value swapped in from high has not been inspected, so advancing skips it and corrupts the partition. The correct rule: advance mid on the less and equal branches, never on the greater branch.

Other pitfalls:

• Loop bound: the condition must be mid <= high (inclusive). Using mid < high leaves the final element unprocessed.
• Not stable: if elements carry payloads and relative order of equal keys matters, this algorithm will reorder them; use a stable method instead.
• Only three groups: it partitions around a single pivot value. For k>3 distinct groups you recurse (as in 3-way quicksort) or use a different multi-way scheme.

Its significance is conceptual as much as practical: Dijkstra used it as a showcase for loop-invariant reasoning — you prove correctness by showing the four-region invariant holds before and after each step. That discipline, plus the concrete speedup on duplicate-heavy data, is why the pattern endures fifty years on.

Dutch National Flag vs. alternative ways to partition a three-valued array

Approach	Passes	Extra space	Stable?	Handles many duplicates
Dutch National Flag (3-way)	1 pass	O(1)	No	Excellent — equals grouped, skipped in recursion
Counting sort (2-pass)	2 passes	O(1) for 3 counts	Can be stable	Excellent, but needs known small key range
Lomuto 2-way partition	1 pass	O(1)	No	Poor — duplicates cause O(n^2) quicksort
Hoare 2-way partition	1 pass	O(1)	No	Fair — better than Lomuto, still no equal band
Sort then scan	O(n log n)	O(1)–O(n)	Depends	Works but asymptotically worse than O(n)