Sort Colors Two Pointer Dutch Flag in DSA C

Mental Model

We separate three colors by moving pointers that divide the array into parts for each color.

Analogy: Imagine sorting red, white, and blue balls into three boxes by moving balls one by one to the correct box using two hands.

Index: 0  1  2  3  4  5  6
Array: R  W  B  W  R  B  W
Pointers:
 low ↑ mid ↑ high ↑

Dry Run Walkthrough

Input: array: [2, 0, 2, 1, 1, 0]

Goal: Sort the array so that all 0s come first, then 1s, then 2s

Step 1: Check mid=0 (value 2), swap with high=5 (value 0), decrease high

[2, 0, 2, 1, 1, 0]
 low=0 mid=0 high=5
After swap:
[0, 0, 2, 1, 1, 2]
 low=0 mid=0 high=4

Why: We move 2 to the end because 2s belong at the right side

Step 2: Check mid=0 (value 0), swap with low=0 (value 0), increase low and mid

[0, 0, 2, 1, 1, 2]
 low=0 mid=0 high=4
After swap:
[0, 0, 2, 1, 1, 2]
 low=1 mid=1 high=4

Why: 0s belong at the left side, so we move low and mid forward

Step 3: Check mid=1 (value 0), swap with low=1 (value 0), increase low and mid

[0, 0, 2, 1, 1, 2]
 low=1 mid=1 high=4
After swap:
[0, 0, 2, 1, 1, 2]
 low=2 mid=2 high=4

Why: Continue moving 0s to the left

Step 4: Check mid=2 (value 2), swap with high=4 (value 1), decrease high

[0, 0, 2, 1, 1, 2]
 low=2 mid=2 high=4
After swap:
[0, 0, 1, 1, 2, 2]
 low=2 mid=2 high=3

Why: Move 2 to the right side

Step 5: Check mid=2 (value 1), increase mid

[0, 0, 1, 1, 2, 2]
 low=2 mid=2 high=3

Why: 1s belong in the middle, so just move mid forward

Step 6: Check mid=3 (value 1), increase mid

[0, 0, 1, 1, 2, 2]
 low=2 mid=3 high=3

Why: Continue moving mid forward for 1s

Step 7: mid=4 is greater than high=3, stop

[0, 0, 1, 1, 2, 2]

Why: Sorting is complete when mid passes high

Result:

[0, 0, 1, 1, 2, 2]

Annotated Code

DSA C

#include <stdio.h>

void sortColors(int* nums, int numsSize) {
    int low = 0, mid = 0, high = numsSize - 1;
    while (mid <= high) {
        if (nums[mid] == 0) {
            int temp = nums[low];
            nums[low] = nums[mid];
            nums[mid] = temp;
            low++;
            mid++;
        } else if (nums[mid] == 1) {
            mid++;
        } else { // nums[mid] == 2
            int temp = nums[mid];
            nums[mid] = nums[high];
            nums[high] = temp;
            high--;
        }
    }
}

void printArray(int* nums, int size) {
    for (int i = 0; i < size; i++) {
        printf("%d", nums[i]);
        if (i != size - 1) printf(" -> ");
    }
    printf(" -> null\n");
}

int main() {
    int nums[] = {2, 0, 2, 1, 1, 0};
    int size = sizeof(nums) / sizeof(nums[0]);
    sortColors(nums, size);
    printArray(nums, size);
    return 0;
}

while (mid <= high) {

continue sorting until mid passes high

if (nums[mid] == 0) {

found 0, swap with low to move 0 to left

low++; mid++;

advance low and mid pointers after placing 0

else if (nums[mid] == 1) {

1 is in correct middle place, just move mid

mid++;

advance mid pointer for 1

else { // nums[mid] == 2

found 2, swap with high to move 2 to right

high--;

decrease high pointer after placing 2

Output

0 -> 0 -> 1 -> 1 -> 2 -> 2 -> null

Complexity Analysis

Time: O(n) because we scan the array once with mid pointer

Space: O(1) because sorting is done in place without extra space

vs Alternative: Compared to counting sort which uses extra space, this uses constant space and one pass

Edge Cases

empty array

function does nothing and exits safely

DSA C

while (mid <= high) {

array with all same colors

array remains unchanged after sorting

DSA C

if (nums[mid] == 0) { ... } else if (nums[mid] == 1) { ... } else { ... }

array with only two colors

algorithm correctly sorts the two colors by swapping

DSA C

while (mid <= high) {

When to Use This Pattern

When you see a problem asking to sort three distinct values quickly and in place, use the Dutch National Flag two-pointer pattern to separate them efficiently.

Common Mistakes

Mistake: Incrementing mid pointer after swapping with high when nums[mid] == 2
Fix: Do not increment mid after swapping with high because the swapped element needs to be checked

Mistake: Swapping incorrectly between pointers causing infinite loops
Fix: Always swap nums[mid] with nums[low] or nums[high] carefully and update pointers accordingly

Summary

Sorts an array of 0s, 1s, and 2s in one pass using two pointers.

Use when you need to sort three distinct values efficiently without extra space.

The key is to maintain three regions with pointers low, mid, and high to separate colors.