Dutch National Flag — Three-Way Partition

What does it solve?

Sort an array containing only 0s, 1s and 2s (Dijkstra's "Dutch national flag") in one pass, in place. The naive fix is counting sort in two passes; this does it in one.

Key insight: keep three pointers. low is the boundary of the 0s region, high the boundary of the 2s region, and mid scans. See a 0 → swap into low and advance both; a 2 → swap into high and shrink high (don't advance mid, the swapped-in value is unexamined); a 1 → just advance mid. Everything settles as O(N) time, O(1) space.

The core idea

// three-way partition, one pass
low=0, mid=0, high=n-1
while mid <= high:
  a[mid]==0 → swap(low,mid); low++; mid++
  a[mid]==1 → mid++
  a[mid]==2 → swap(mid,high); high--

Complexity

Time complexity

O(N)

A single pass: mid and high converge, and every index is examined at most once. No counting phase, no second sweep.

Space complexity

O(1)

Sorted in place with three integer pointers. No buckets, no output array.

Examples & edge cases

Live animation — three pointers partition into 0s · 1s · 2s

0s [0 … low) 1s [low … mid) unknown [mid … high] 2s (high … end]

low boundary mid (scanning) high boundary swapping

Array of 0/1/2

Current step detail

low = — mid = — high = — swaps = —

Step — of —

low

—

end of 0s

mid

—

scan pointer

high

—

start of 2s

swaps done

—

so far

Select an example and press Play to start.

✓ Done

Speed Medium

Step-by-step table

Step	low	mid	high	a[mid]	Rule	Action	Array

C++ implementation

dutch_national_flag.cpp

#include <bits/stdc++.h>
using namespace std;

// Sort an array of 0s, 1s, 2s in one pass (Dutch National Flag)
void sortColors(vector<int>& a) {
    int low = 0, mid = 0, high = (int)a.size() - 1;

    while (mid <= high) {
        if (a[mid] == 0) {
            swap(a[low], a[mid]);   // send 0 to the front region
            low++; mid++;
        } else if (a[mid] == 1) {
            mid++;                  // 1 is already in the middle region
        } else {                    // a[mid] == 2
            swap(a[mid], a[high]);  // send 2 to the back region
            high--;                 // DON'T advance mid: swapped-in value is unseen
        }
    }
}

int main() {
    vector<int> a = {2,0,2,1,1,0};
    sortColors(a);
    for (int x : a) cout << x << " "; // 0 0 1 1 2 2
    return 0;
}

My Notes

📝 Notes ✅

▼

● Start typing to save... 0 chars