How to Learn the Dutch National Flag Algorithm: Three-Way Partitioning, Loop Invariants, Duplicate Keys and Production Quicksort

Quick read: The Dutch National Flag algorithm turns an array containing three classes of values into three contiguous regions in one linear scan and constant extra space. The important lesson is not the colours. It is the discipline of maintaining a loop invariant while several boundaries move at once.

One-sentence answer: keep a left boundary for items known to belong in the first group, a scanning pointer for unclassified items, and a right boundary for items known to belong in the third group; every step shrinks the unknown region until nothing remains.

Why this small algorithm is worth learning

Many beginning programmers think an algorithm is mainly a sequence of commands. The Dutch National Flag problem teaches something deeper: a good algorithm is often a collection of statements that stay true while the program changes the data. Those statements are invariants. Once you can see them, code that first looked like pointer magic becomes almost mechanical.

That makes this a useful bridge from beginner programming to professional algorithm engineering. At beginner level, it is a sorting puzzle. At intermediate level, it is an exercise in arrays, swaps and boundary conditions. At advanced level, it becomes a study of correctness proofs and partition schemes. In production, the same idea appears in duplicate-aware quicksort and in systems that repeatedly classify records into a small number of categories.

1. Start without code: three boxes on a table

Imagine cards labelled 0, 1 and 2. Your goal is to place all 0s first, then all 1s, then all 2s. You could count the cards and rewrite the array, but that needs a different mental model. The Dutch National Flag method instead rearranges the original array in place.

At any moment, divide the array into four regions:

left region: already known to contain only 0s;
middle-left region: already known to contain only 1s;
unknown region: not classified yet;
right region: already known to contain only 2s.

Use three indices: low, mid and high. Everything before low is a 0. Everything from low up to but not including mid is a 1. Everything after high is a 2. The interval from mid through high is the only part we have not yet classified.

2. The three cases

Inspect a[mid].

If it is 0, swap it with a[low], then increment both low and mid.
If it is 1, it is already in the correct middle region, so increment mid.
If it is 2, swap it with a[high] and decrement high. Do not increment mid yet, because the value just swapped in from the right has not been classified.

That last sentence is where many implementations fail. A swap from the right does not magically make the new a[mid] correct. It must be inspected on the next iteration.

3. A complete trace

Take [2, 0, 2, 1, 1, 0]. Initially low = 0, mid = 0, high = 5.

a[mid] = 2. Swap positions 0 and 5 → [0, 0, 2, 1, 1, 2]. Decrease high to 4. Keep mid = 0.
a[mid] = 0. Swap positions 0 and 0. Increase low to 1 and mid to 1.
a[mid] = 0. Swap positions 1 and 1. Increase low to 2 and mid to 2.
a[mid] = 2. Swap positions 2 and 4 → [0, 0, 1, 1, 2, 2]. Decrease high to 3.
a[mid] = 1. Increase mid to 3.
a[mid] = 1. Increase mid to 4.

Now mid > high. The unknown region is empty, so the algorithm is finished.

4. Python implementation

def dutch_flag(a):
    low = 0
    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
        elif a[mid] == 2:
            a[mid], a[high] = a[high], a[mid]
            high -= 1
        else:
            raise ValueError("expected only 0, 1, or 2")

    return a

Notice how closely the code follows the invariant. There is no clever hidden trick. Each branch merely places one observed value into a region whose meaning is already defined.

5. The invariant is the real algorithm

Before every loop iteration, we want all four statements to be true:

all indices smaller than low contain 0;
all indices from low to mid - 1 contain 1;
all indices from mid to high are unclassified;
all indices larger than high contain 2.

A correctness argument then has three parts. Initialization: at the start, the known regions are empty, so the claims are trivially true. Maintenance: each of the three cases moves one item into the appropriate known region without breaking the others. Termination: the loop ends when mid > high, which means the unknown region is empty. The known regions then cover the entire array.

This proof pattern—initialization, maintenance, termination—is one of the most transferable habits in algorithm study. Learn it here on six integers, and you are preparing yourself for binary search, partition-based selection, graph traversals and concurrent data structures.

6. Complexity: why one pass matters

Every iteration shrinks the unknown region by one element. Therefore the running time is O(n). The algorithm uses only a fixed number of indices and temporary values, so its auxiliary space is O(1).

It is also in-place, but it is not stable: equal-class items may change relative order because of swaps. That distinction matters professionally. “Linear time” and “constant space” are not enough to choose an algorithm. You also ask whether order among equal elements must be preserved, whether writes are expensive, whether data are mutable and whether concurrency changes the cost model.

7. From three colours to a three-way partition around a pivot

The powerful generalization is to replace the literal values 0, 1 and 2 with three comparisons against a pivot p:

values less than p;
values equal to p;
values greater than p.

This is the connection to three-way quicksort. Ordinary two-way partitioning can behave wastefully when many keys equal the pivot. A three-way partition collects equals into one middle block, so recursive calls need only process the less-than and greater-than regions. Princeton’s Algorithms materials use this approach in their Quick3way implementation.

8. What beginners usually get wrong

Incrementing mid after swapping with high. The incoming element is still unknown.
Using mid < high rather than mid <= high. That can leave the final unknown element unclassified.
Remembering code without remembering regions. If you forget what each interval means, one off-by-one error becomes hard to diagnose.
Assuming “in place” means “stable”. It does not.
Testing only mixed inputs. All-zero, all-one, all-two, empty and single-element inputs reveal boundary mistakes quickly.

9. A professional testing ladder

Do not test only the final output. Test the claims the algorithm makes.

Example tests: empty list, one item, already grouped, reverse grouped and many duplicates.
Permutation property: the output must contain exactly the same multiset of values as the input.
Ordering property: no 1 may appear before a later 0, and no 2 may appear before a later 0 or 1.
Invariant assertions: in a teaching implementation, assert the four region properties during each iteration.
Differential testing: compare the result against sorted(a) for thousands of randomly generated 0/1/2 arrays.

Professionals frequently move from example-based testing to property-based testing because an algorithm is defined by properties, not by one memorable sample.

10. How to study this algorithm efficiently

Programming-education research gives a useful sequence for learning procedural ideas. First predict what a short trace will do. Then run it and compare. Next investigate the role of each pointer, modify one condition, and finally make your own version. This resembles the PRIMM teaching approach studied in school programming education. Subgoal-labelled worked examples can also help: instead of memorising five lines of code, label the purposes “grow left region”, “accept middle value”, and “grow right region”. Parsons-style tasks—reordering shuffled code blocks—are another useful bridge before writing the whole implementation from memory.

A strong learner should be able to do four things without looking at the code: draw the four regions, state the invariant, explain why mid does not move after the third-case swap, and derive the stopping condition. If those are secure, the syntax is the easy part.

11. Practice ladder: beginner to professional

Beginner: trace five iterations on paper and colour the four regions after each step.
Developing: implement the 0/1/2 version without copying.
Intermediate: generalize it to three categories defined by a classifier function.
Advanced: implement three-way partitioning around a pivot and use it inside quicksort.
Professional: benchmark two-way and three-way quicksort on datasets with different duplicate rates; measure comparisons, swaps, recursion depth and wall-clock time, and explain when the extra branch structure pays for itself.

12. Where this idea appears in the wider algorithm world

The Dutch National Flag algorithm belongs to a wider family of partition-and-maintain-an-invariant techniques. Quickselect partitions around a pivot. Quicksort partitions before recursion. Two-pointer algorithms maintain regions of processed and unprocessed data. Even some garbage collectors, stream processors and compaction procedures can be understood as maintaining boundaries between categories while consuming an unknown region.

The transferable question is therefore not “Where will I ever sort red, white and blue objects?” It is: Can I describe the regions of my data so clearly that every update preserves their meaning? That is a professional algorithmic habit.

Sources and further reading

Final idea: Learn the invariant first, the pointer movements second and the code third. If you can explain why every element leaves the unknown region exactly once, you understand the Dutch National Flag algorithm rather than merely remembering it.

Small Group Tutorials