The Dutch National Flag

The shape of the problem

The classical statement: given an array containing only the values 0, 1, and 2 (red, white, blue), sort it in-place in a single pass with constant extra memory. Standard sorting algorithms either use too much memory (merge sort) or too many comparisons (quicksort's O(n log n) is overkill when there are only three distinct values). The Dutch national flag algorithm runs in O(n) time and O(1) memory and uses each comparison productively.

The technique generalises immediately to: any in-place partition where the alphabet is small and known in advance. Sort by sign (negative · zero · positive). Move zeroes to the end. Partition around a pivot for quicksort. The three-pointer dance is the same in each case.

The loop invariant

The whole algorithm is an exercise in maintaining a precise invariant. At every iteration:

• a[0..lo) contains only 0s.
• a[lo..mid) contains only 1s.
• a[mid..hi] is the unprocessed region, values unknown.
• a[hi+1..n) contains only 2s.

The boundaries are half-open at lo and mid, closed at hi. We initialise lo = mid = 0 and hi = n − 1, so the unprocessed region starts as the whole array. The loop runs while mid ≤ hi, the unprocessed region is non-empty.

Implementation

def sort_colors(a):
    lo, mid, hi = 0, 0, len(a) - 1
    while mid <= hi:
        if a[mid] == 0:
            a[lo], a[mid] = a[mid], a[lo]
            lo += 1
            mid += 1
        elif a[mid] == 1:
            mid += 1
        else:                                # a[mid] == 2
            a[mid], a[hi] = a[hi], a[mid]
            hi -= 1
            # don't advance mid - the swapped-in value is still unprocessed

The three branches handle the three cases. Two of them are straightforward; the third has a subtle asymmetry worth dwelling on.

The 0 case, swap and advance both

If a[mid] == 0, it belongs in the low region. Swap with a[lo], then advance both lo and mid. Why both? Because the value previously at a[lo] was a 1 (it was inside the 1s region by invariant), and now it's at a[mid] and confirmed as a 1, no need to re-examine. Advancing mid is safe.

The 1 case, just advance mid

If a[mid] == 1, it's already in its correct region; the 1s region simply grows by one. Advance mid; nothing else changes.

The 2 case, swap and DO NOT advance mid

If a[mid] == 2, it belongs in the high region. Swap with a[hi], then decrement hi. Do not advance mid. The value swapped in from a[hi] has not been examined yet, it could be any of 0, 1, or 2. We need to re-process it next iteration. This asymmetry between the 0 case (advance mid) and the 2 case (do not) is the algorithm's only non-obvious step. Forgetting it produces wrong answers on inputs like [2, 0, 1].

A worked trace

Run on [2, 0, 2, 1, 1, 0]. Initial state: lo=0, mid=0, hi=5.

step 1: a[0]=2 → swap a[0],a[5]; hi=4
        a = [0, 0, 2, 1, 1, 2]   lo=0, mid=0, hi=4
step 2: a[0]=0 → swap a[0],a[0]; lo=1, mid=1
        a = [0, 0, 2, 1, 1, 2]   lo=1, mid=1, hi=4
step 3: a[1]=0 → swap a[1],a[1]; lo=2, mid=2
        a = [0, 0, 2, 1, 1, 2]   lo=2, mid=2, hi=4
step 4: a[2]=2 → swap a[2],a[4]; hi=3
        a = [0, 0, 1, 1, 2, 2]   lo=2, mid=2, hi=3
step 5: a[2]=1 → mid=3
        a = [0, 0, 1, 1, 2, 2]   lo=2, mid=3, hi=3
step 6: a[3]=1 → mid=4
        a = [0, 0, 1, 1, 2, 2]   lo=2, mid=4, hi=3 → loop ends

Sorted in 6 steps for an array of 6 elements. Each iteration moves one pointer; the loop terminates when mid > hi.

Complexity, reasoned

Each iteration does a constant amount of work and either advances mid (in the 0 and 1 cases) or shrinks the unprocessed region by decrementing hi (in the 2 case). Either way, the unprocessed region shrinks by one. The region starts with n elements and ends with zero, so the loop runs at most n times. Time: O(n). Memory: O(1), three indices and one scalar for the swap.

Where the technique reappears

Quicksort's three-way partition

Standard quicksort's two-way partition degrades to O(n²) on inputs with many duplicates, because each duplicate forces a recursion on its own. The three-way partition (also called "fat partition") splits into less-than · equal · greater regions using exactly the Dutch flag dance. The "equal" region doesn't get recursed on, duplicates are handled in the partition step itself. This single change makes quicksort robust to duplicate-heavy inputs.

Move zeroes to the end

"Move all zeroes to the end while preserving relative order of non-zeroes" is a two-region simplification, non-zero region grows from the left, zero region grows from the right. Same machinery, one fewer pointer.

Sort by sign

Partition negatives, zeroes, and positives. Same structure as red-white-blue. The signal: any small fixed alphabet supports the same in-place partition.

When to reach for it

Whenever the alphabet is small and fixed, the array is mutable, and you want O(n) time with O(1) space. If the alphabet is large or unknown, you need a comparison sort (or counting sort if the values are bounded integers, see Sorting & Search). If you need to preserve the relative order of equal elements (a stable sort), Dutch flag does not, the swaps cross equal values arbitrarily. Use a stable counting sort instead.

Where beginners go wrong

• Advancing mid in the 2 case. Causes wrong answers on inputs with consecutive 2s. The swapped-in value at mid has not been examined and must be processed before mid moves.
• Loop condition mid < hi instead of mid ≤ hi. Misses the last unprocessed element when the array has odd length and the final value is at the boundary.
• Initialising hi = n instead of n − 1. Off-by-one; you'll swap with an out-of-bounds index.
• Trying to use the technique with > 3 distinct values. The three-pointer structure breaks down. For a small bounded alphabet, use counting sort; for an arbitrary alphabet, use a comparison sort.

What to read next

The Sorting & Search module covers counting sort and comparison sorts as the broader context. Dutch flag is the in-place specialisation that beats both for tiny alphabets. Prefix sums share the spirit of "small idea, broad reach". And the Two Pointers module formalises the three-pointer pattern as one of the recurring shapes in array problems.