Dutch National Flag

The Idea

With only three distinct values, sorting is really partitioning. Hold three walls: everything before low is the small value, everything after high is the large one, and the stretch from i to high is still unseen. Read the value at i and push it to the wall it belongs behind. A swap with high pulls in a value nobody has looked at, so the cursor must stay put for one more read.

Real-World Example

A returns desk sorting a bin into restock, inspect and scrap. Restock goes into the crate on the left, scrap into the crate on the right, inspect stays in the middle. Every item is handled exactly once.

The Code

def sort_colors(nums):
    low, i, high = 0, 0, len(nums) - 1
    while i <= high:
        if nums[i] == 0:                        # belongs in the front block
            nums[low], nums[i] = nums[i], nums[low]
            low += 1
            i += 1
        elif nums[i] == 2:                      # belongs in the back block
            nums[high], nums[i] = nums[i], nums[high]
            high -= 1                           # i stays: that value is unseen
        else:
            i += 1
    return nums

print(sort_colors([2, 0, 1, 2, 0]))   # [0, 0, 1, 2, 2]