Dutch national flag
mediumThree pointers carve the array into four regions, and the loop shrinks the unknown one to nothing. The one line everyone gets wrong: on a 2, mid does not advance.
O(n)Space O(1)Saved in this browser - no sign-up, nothing sent anywhere.
How dutch national flag works
Three pointers carve the array into four regions: a[0..low-1] holds settled 0s, a[low..mid-1] settled 1s, a[mid..high] is unexamined, and a[high+1..n-1] holds settled 2s. Each iteration classifies a[mid] into one of three branches, every branch preserves the invariant, and the loop ends when the unknown region is empty. Stating that invariant is most of the correctness proof.
The asymmetry is the entire subtlety. On a 0, the element swapped up from low is a settled 1 (or the element itself), so mid may advance. On a 2, the element swapped in from high has never been examined - it could be anything - so mid must stay and look at it next iteration. That one line is where implementations break.
The accounting is exact: every iteration either advances mid or lowers high, so the gap closes by one each time and the loop runs exactly n iterations with at most one swap each. Counting sort also handles three values in O(n) but takes two passes; Dijkstra's version takes one, and it is the three-way partition quicksort uses to survive duplicate-heavy arrays.
Step by step
- Sort 2, 0, 1, 2, 0. Start low = 0, mid = 0, high = 4 - the whole array is unknown.
- a[0] = 2: swap it with a[4] and lower high to 3. The array is now 0, 0, 1, 2, 2 - and mid stays, because the incoming 0 is unexamined.
- a[0] is now 0: it already sits where the 0s region grows, so low and mid both advance to 1.
- a[1] = 0 as well - the swap is with itself, and low and mid advance to 2.
- a[2] = 1: already in the right region, so only mid advances, to 3. No swap needed.
- a[3] = 2 with high = 3: swap in place and lower high to 2. mid now exceeds high - done: 0, 0, 1, 2, 2 in exactly five examinations.
Complexity
| Worst case time | O(n) |
|---|---|
| Space | O(1) |
Reference implementation
Python
def sort_colors(a):
"""Sort an array of 0s, 1s and 2s in a single pass."""
low = mid = 0
high = 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], a[high] = a[high], a[mid]
high -= 1 # do NOT advance mid: the swapped-in
# value has not been examined yetJavaScript
function sortColors(a) {
let low = 0, mid = 0, high = a.length - 1;
while (mid <= high) {
if (a[mid] === 0) {
[a[low], a[mid]] = [a[mid], a[low]]; low++; mid++;
} else if (a[mid] === 1) {
mid++;
} else {
[a[mid], a[high]] = [a[high], a[mid]]; high--; // mid stays
}
}
return a;
}Worth noticing
Four regions, and the invariant names them
a[0..low−1] is all 0s, a[low..mid−1] is all 1s, a[mid..high] is unexamined, a[high+1..] is all 2s. Every branch preserves that, and the loop ends when the unknown region is empty. Stating the invariant is most of the proof.
Why mid does not advance on a 2
The value swapped in from `high` has never been looked at - it could be anything. Advancing mid would skip it. This is the one line people get wrong, and it is why the 0-case and the 2-case are not symmetric.
One pass instead of counting sort's two
Counting the three values then rewriting the array also works and is also O(n). Dijkstra's version does it in a single pass with O(1) extra space and no second traversal - and it is the partition step three-way quicksort uses to handle duplicate pivots.
Common pitfalls
- Advancing mid after the 2-swap. The value pulled down from high is unexamined - skip it and a stray 0 or 2 survives in the middle. This is the classic bug.
- Looping while mid < high instead of mid <= high, which leaves the element where the pointers meet unclassified.
- Adding the same caution to the 0-branch. It is unnecessary there: everything below mid is already classified, so the element swapped up is a known 1 or the element itself.
- Stretching it past three values. The four-region invariant is specific to three categories; four or more need a different partition scheme or a real sort.
Where it is used
- Sort Colors, LeetCode 75 - the problem is this algorithm restated with red, white and blue.
- The three-way partition inside quicksort, which keeps duplicate-heavy inputs from degrading to O(n²).
- Any in-place three-bucket grouping: negative, zero, positive, or less-than, equal, greater-than a pivot.
- Two-value versions - move zeroes, segregate 0s and 1s - are the same machinery with one region removed.
Frequently asked questions
What are the time and space complexity of the Dutch national flag algorithm?
O(n) time: every iteration either advances mid or lowers high, so the gap closes by one per step and the loop runs exactly n times, with at most one swap each. Space is O(1) - three indices, no counting array, no second buffer.
Why does mid not advance when it sees a 2?
The swap brings a[high]'s value to position mid, and that value has never been examined - it might be a 0 that still needs to travel to the front. mid stays so the next iteration can classify it. In the 0-branch the incoming value is a known 1, which is why that branch does advance.
How is this different from counting sort?
Counting sort tallies the three values and then rewrites the array: two traversals, and it rebuilds values rather than moving elements. The flag algorithm sorts in a single pass by swapping the actual elements - which matters when they are records keyed by 0, 1, 2 - with O(1) extra space.
Where does the name come from?
Edsger Dijkstra posed it as arranging pebbles of three colours into bands like the Dutch tricolour. The array version keeps the image: 0s, 1s and 2s ending as three contiguous bands. The same idea generalises to three-way partitioning around any pivot.