The Dutch National Flag algorithm (invented by Edsger W. Dijkstra) is the secret weapon that makes 3-way QuickSort resilient against duplicate keys.

1. The 3 Pointer Invariant

We divide the array into 4 distinct regions using 3 pointers: low, mid, and high:

[ 0 ... low-1 ]  -> All elements strictly 0
[ low ... mid-1 ] -> All elements strictly 1
[ mid ... high ]  -> UNKNOWN (yet to be inspected)
[ high+1 ... n-1] -> All elements strictly 2

Initially, low = 0, mid = 0, and high = n - 1. The entire array is initially inside the UNKNOWN region.

2. The 3 State Transitions

While mid <= high, inspect nums[mid]:

1. If nums[mid] == 0: Swap nums[low] with nums[mid]. Increment BOTH low++ and mid++.
   Why can we increment mid here? Because whatever was sitting at low was already processed (it was guaranteed to be a 1).
2. If nums[mid] == 1: It’s already in the right spot! Just increment mid++.
3. If nums[mid] == 2: Swap nums[mid] with nums[high]. Decrement high--.
   THE CRITICAL CATCH: Do NOT increment mid here! Whatever came from high was unknown—it might be a 0, a 1, or another 2! We must inspect it on the next loop iteration!

Clean Python 3.12 Implementation

def sort_colors(nums: list[int]) -> None:
    """In-place 3-way partition in O(N) time and O(1) memory."""
    low = 0
    mid = 0
    high = len(nums) - 1

    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif nums[mid] == 1:
            mid += 1
        else: # nums[mid] == 2
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1
            # Note: mid is intentionally NOT incremented here!

Complexity Breakdown

• Time Complexity: O(N). In every single step, either mid increases or high decreases. The unknown window (high - mid) strictly shrinks to zero in at most N steps.
• Space Complexity: O(1). No extra memory allocated.