Dutch National Flag

Problem (Dijkstra). Given an array of three values — say 0, 1, 2 — sort it in one pass with $O(1)$ extra space.

The three-pointer partition

void dutchFlag(vector<int>& a) {
    int low = 0, mid = 0, high = a.size() - 1;
    while (mid <= high) {
        if      (a[mid] == 0) swap(a[low++], a[mid++]);
        else if (a[mid] == 1) mid++;
        else                  swap(a[mid], a[high--]);    // do NOT advance mid
    }
}

The invariant, at every step:

[0, low)      all 0s
[low, mid)    all 1s
[mid, high]   unexamined
(high, n)     all 2s

Do not advance mid on the 2-case

The element swapped in from high has not been examined yet. Advancing mid skips it — the single most common bug in this algorithm.

$O(n)$ time, $O(1)$ space, one pass.

Why it matters: three-way quicksort

The same partition makes quicksort $O(n)$ on arrays with many duplicates, by grouping elements equal to the pivot into their own region:

void quicksort3(vector<int>& a, int lo, int hi) {
    if (lo >= hi) return;
    int pivot = a[lo + rng() % (hi - lo + 1)];
    int lt = lo, i = lo, gt = hi;
    while (i <= gt) {
        if      (a[i] < pivot) swap(a[lt++], a[i++]);
        else if (a[i] > pivot) swap(a[i], a[gt--]);
        else                   i++;
    }
    quicksort3(a, lo, lt - 1);
    quicksort3(a, gt + 1, hi);                            // skip the equal block
}

An array of $n$ identical elements sorts in $O(n)$ instead of $O(n^2)$ — and this is why std::sort uses a three-way partition internally. It is also the right choice for radix-style string sorting (three-way radix quicksort).

Two-way partitioning

The Lomuto and Hoare schemes are the two-value cases:

// Lomuto: simpler, more swaps
int lomuto(vector<int>& a, int lo, int hi) {
    int pivot = a[hi], i = lo;
    for (int j = lo; j < hi; j++) if (a[j] < pivot) swap(a[i++], a[j]);
    swap(a[i], a[hi]);
    return i;
}
 
// Hoare: fewer swaps, faster in practice
int hoare(vector<int>& a, int lo, int hi) {
    int pivot = a[lo], i = lo - 1, j = hi + 1;
    while (true) {
        do i++; while (a[i] < pivot);
        do j--; while (a[j] > pivot);
        if (i >= j) return j;
        swap(a[i], a[j]);
    }
}

Hoare’s version does about three times fewer swaps and degrades more gracefully on duplicates, but returns a split point rather than the pivot’s final position — a common source of off-by-one errors.

Applications of partitioning

Task	Partition use
Sort 3 distinct values	Dutch flag
Quicksort with duplicates	three-way partition
nth_element / quickselect	partition, recurse on one side only
Median of medians	partition around a good pivot
Move all zeros to the end	two-pointer partition
Segregate even and odd	two-pointer partition
Group by a predicate, stable	std::stable_partition
Sort colours / categories	Dutch flag generalised to $k$ groups

For $k$ groups with $k>3$, a counting sort ($O(n+k)$) is simpler and faster than a $k$-way partition.

Quickselect — the close relative

int quickselect(vector<int>& a, int k) {                  // k-th smallest, 0-indexed
    int lo = 0, hi = a.size() - 1;
    while (true) {
        int p = hoare(a, lo, hi);
        if (k <= p) hi = p; else lo = p + 1;
    }
}

$O(n)$ expected — and std::nth_element is exactly this (introselect, falling back to median-of-medians for the worst case). Use it whenever you need the $k$-th element but not a full sort.

Why it is worth knowing

Two reasons:

1. The invariant discipline. Dijkstra’s original presentation is the textbook example of writing a loop by stating its invariant first and deriving the body from it. If you can state the four regions, the code is forced.
2. Three-way partitioning is genuinely important. Arrays with few distinct values are common, and the difference between $O(n\log n)$ and $O(n^2)$ on them is the difference between accepted and TLE.

See also: Sorting · Two Pointers · STL Containers