Definition

The Dutch National Flag problem sorts an array of only 0s, 1s, and 2s (likened to red, white, blue) into 0 → 1 → 2 order in a single pass with no extra memory. It is a classic 3-way partitioning technique proposed by Dijkstra.

Key Characteristics

• ✓Three pointers (low/mid/high) split the array into 0-zone, 1-zone, unknown, and 2-zone
• ✓Sorts in a single pass — O(n) time, O(1) extra space
• ✓Only applicable when there are exactly three distinct values (not a general comparison sort)
• ✓Unstable sort — original order of equal elements is not preserved

Time Complexity