Dutch national flag (sort 0/1/2) Explained: Sorting [2, 0, 2, 1, 1, 0]

Imagine you are handed an array of colored pebbles where every pebble is colored either red, white, or blue. In our locked working example, the array is given as $\text{nums}=[2,0,2,1,1,0]$, representing a chaotic mix of three distinct values. Your job is to group them so all the 0s come first, followed by all the 1s, and finally all the 2s, resulting in $[0,0,1,1,2,2]$. If you reach for a standard comparison-based sorting algorithm like merge sort or quicksort, you will waste time comparing elements that you already know can only be 0, 1, or 2. Even worse, a general sort takes $O(n\log n)$ time and often requires extra memory, while we need to do this in-place with a single pass through the array. Without a specialized strategy, dealing with interleaved values like our initial $[2,0,2,1,1,0]$ forces clumsy multi-pass filtering where you scan once for 0s, scan again for 1s, and rewrite the array.

When working with the locked example $\text{nums}=[2,0,2,1,1,0]$, a standard sorting algorithm takes $O(n\log n)$ time, which misses a crucial constraint: we only have three unique values ($0,1,$ and 2). Instead of comparing elements against each other arbitrarily, we can maintain three distinct pointers—$\text{low}$, $\text{i}$, and $\text{high}$—to carve the array into four contiguous regions:

Let us execute our three-pointer model on the locked example: $\text{nums}=[2,0,2,1,1,0]$ with $n=6$. We initialize $\text{low}=0$, $i=0$, and $\text{high}=5$. At each step, we examine the element at $\text{nums}[i]$ and apply our three pointer rules until $i>\text{high}$.

Now that you have seen the exact mechanics of how the three pointers ($\text{low},\text{i},$ and $\text{high})$ handle the standard working example $\{2,0,2,1,1,0\}$, it is time to test your own predictive intuition. Consider a slightly modified starting array: $\{2,0,1,2,0\}$. Set your initial pointers at $\text{low}=0,\text{i}=0,$ and $\text{high}=4,$ and step through the first two iterations manually. Pay special attention to what happens when $\text{i}$ encounters a 0 versus when it encounters a 2, and note why the pointer $\text{high}$ decreases without advancing $\text{i}$ when a 2 is swapped.

def sort_colors_practice(nums):
    low, i, high = 0, 0, len(nums) - 1
    # Trace what nums looks like after i processes the first two elements:
    # nums = [2, 0, 1, 2, 0]
    pass

We have successfully tracked our initial array $\{2,0,2,1,1,0\}$ through a single-pass three-pointer scan, transforming it into $\{0,0,1,1,2,2\}$. But the Dutch National Flag algorithm is more than a one-off trick for sorting three specific integer codes. The core mental model—maintaining boundaries with pointers while sweeping an active cursor through uncharted territory—is a universal blueprint for array segregation. Whenever you need to separate data into discrete buckets in linear time and constant space, you are essentially adapting this exact pointer-boundary invariant.