Partition / Dutch National Flag (Two Pointers Sub-pattern)

// Dutch National Flag: sort 0s, 1s and 2s in one pass.
// [0 .. low-1] = 0s, [low .. mid-1] = 1s, [mid .. high] = unknown, [high+1 .. n-1] = 2s
void dutchFlag(vector<int>& a) {
    int low = 0, mid = 0, high = (int)a.size() - 1;
    while (mid <= high) {
        if (a[mid] == 0) swap(a[low++], a[mid++]);   // a 0 joins the left region
        else if (a[mid] == 1) mid++;                 // a 1 is already in place
        else swap(a[mid], a[high--]);                // a 2 joins the right region; don't move mid —
                                                     // the value swapped in hasn't been checked yet
    }
}