Dutch National Flag — Why mid++ After High Swap Drops Data

Sorting an array with only three distinct values is a constraint that makes generic comparison sorts wasteful. Counting sort works but requires two passes. QuickSort is O(n log n) and overkill. The Dutch National Flag algorithm solves it in a single pass — O(n) time, O(1) space — by maintaining three pointers that carve the array into four live regions as they converge.

The algorithm was proposed by Edsger Dijkstra. It is the foundation of 3-way QuickSort, which handles duplicate-heavy arrays efficiently. The classic problem is LeetCode 75 'Sort Colors', where values are 0, 1, 2 representing red, white, blue.

The critical invariant: at every step, arr[0..low-1] contains only 0s, arr[low..mid-1] contains only 1s, arr[high+1..n-1] contains only 2s, and arr[mid..high] is unexamined. The mid pointer scans forward; low and high converge inward. The single rule that causes 90% of bugs: never increment mid after swapping with high.

Why the Dutch National Flag Algorithm Drops Data After a High Swap

The Dutch National Flag algorithm sorts an array of three distinct values in a single pass with O(n) time and O(1) space. It uses three pointers: low, mid, and high. The core mechanic: when a 2 (high value) is encountered at mid, swap it with the element at high, then decrement high — but do not increment mid. This is the critical detail that prevents data loss. The algorithm partitions the array into three regions: 0s from 0 to low-1, 1s from low to mid-1, and 2s from high+1 to end. The mid pointer scans forward only when the current element is 0 or 1. After swapping a 2 to the end, the element now at mid came from high and hasn't been inspected yet — skipping mid++ ensures it gets processed. This invariant guarantees correctness without extra storage. Use this algorithm when you need to sort three categories in-place with minimal memory — for example, sorting an array of 0s, 1s, and 2s representing three states in a distributed system, or partitioning network packets by priority. It's the fastest known approach for this specific case, beating any comparison-based sort.

How Dutch National Flag Works — Plain English

The Dutch National Flag algorithm sorts an array of three distinct values (0, 1, 2) in O(n) time, O(1) space, single pass.

Three-way partition invariant — three pointers divide the array: arr[0..low-1] = 0s. arr[low..mid-1] = 1s. arr[mid..high] = unknown. arr[high+1..n-1] = 2s.

Step-by-step: 1. Initialize low=0, mid=0, high=n-1. 2. While mid <= high: a. arr[mid]==0: swap arr[low]↔arr[mid], low++, mid++. b. arr[mid]==1: mid++ (already correct region). c. arr[mid]==2: swap arr[mid]↔arr[high], high--. Do NOT advance mid.

Worked example on [2,0,2,1,1,0]: low=0,mid=0,high=5. arr[0]=2: swap arr[0]↔arr[5]→[0,0,2,1,1,2]. high=4. arr[0]=0: swap arr[0]↔arr[0]. low=1,mid=1. arr[1]=0: swap arr[1]↔arr[1]. low=2,mid=2. arr[2]=2: swap arr[2]↔arr[4]→[0,0,1,1,2,2]. high=3. arr[2]=1: mid=3. arr[3]=1: mid=4. mid>high. Done. Result: [0,0,1,1,2,2].

package io.thecodeforge.algo;

import java.util.Arrays;

public class DutchNationalFlag {

    /**
     * Sorts an array of three distinct values (0, 1, 2) in-place.
     * O(n) time, O(1) space, single pass.
     */
    public static void sortColors(int[] arr) {
        if (arr == null || arr.length <= 1) return;

        int low = 0;
        int mid = 0;
        int high = arr.length - 1;

        while (mid <= high) {
            switch (arr[mid]) {
                case 0:
                    swap(arr, low, mid);
                    low++;
                    mid++;
                    break;
                case 1:
                    mid++;
                    break;
                case 2:
                    swap(arr, mid, high);
                    high--;
                    // Do NOT increment mid — swapped element is unexamined
                    break;
            }
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {2, 0, 2, 1, 1, 0};
        System.out.println("Before: " + Arrays.toString(arr));
        sortColors(arr);
        System.out.println("After:  " + Arrays.toString(arr));

        // Edge cases
        sortColors(new int[]{2, 2, 2, 2}); // all 2s
        sortColors(new int[]{0, 0, 0, 0}); // all 0s
        sortColors(new int[]{1, 1, 1, 1}); // all 1s
        sortColors(new int[]{2, 0, 1});    // already one of each
        sortColors(new int[]{});            // empty
        sortColors(new int[]{1});           // single element
    }
}

The Three-Pointer Partition Strategy

The brilliance of the DNF algorithm lies in its ability to maintain four sections within the array using only three pointers: low, mid, and high.

1. [0 ... low-1]: Elements smaller than the pivot (0s).
2. [low ... mid-1]: Elements equal to the pivot (1s).
3. [mid ... high]: Elements yet to be explored (Unknown).
4. [high+1 ... N-1]: Elements larger than the pivot (2s).

We iterate using the mid pointer. When we encounter a 0, we swap it with low and advance both. When we see a 1, we just move mid. When we see a 2, we swap it with high and decrement high—but we don't move mid yet, because the element swapped from the end is still unknown.

package io.thecodeforge.algo;

/**
 * Dutch National Flag Algorithm Implementation
 * Complexity: Time O(n), Space O(1)
 */
public class SortColors {
    public void sort(int[] nums) {
        if (nums == null || nums.length <= 1) return;

        int low = 0;
        int mid = 0;
        int high = nums.length - 1;

        while (mid <= high) {
            switch (nums[mid]) {
                case 0: // Element belongs in the 'Red' zone
                    swap(nums, low++, mid++);
                    break;
                case 1: // Element belongs in the 'White' (middle) zone
                    mid++;
                    break;
                case 2: // Element belongs in the 'Blue' zone
                    swap(nums, mid, high--);
                    // Note: We do NOT increment mid here because the 
                    // swapped element from 'high' is unexamined.
                    break;
            }
        }
    }

    private void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] testCase = {2, 0, 2, 1, 1, 0};
        new SortColors().sort(testCase);
        // Result: [0, 0, 1, 1, 2, 2]
    }
}

DNF as 3-Way QuickSort Partition — The Duplicate-Heavy Optimization

Dutch National Flag is the partition step in Dijkstra's 3-way QuickSort. Standard QuickSort partitions into two zones (< pivot, >= pivot). 3-way QuickSort partitions into three zones (< pivot, == pivot, > pivot). This is critical for arrays with many duplicate elements.

Standard QuickSort on an array of all identical elements: O(n^2) because every partition is maximally unbalanced (all elements go to one side). 3-way QuickSort with DNF: O(n) because all elements are grouped into the == pivot zone in a single pass, and only the < and > zones are recursed on.

The DNF partition in QuickSort uses the pivot value as the 'middle' value. Elements less than pivot go to the low zone, elements equal to pivot go to the mid zone, elements greater than pivot go to the high zone. The mid zone is already sorted and requires no further recursion.

package io.thecodeforge.algo;

import java.util.Arrays;

public class ThreeWayQuickSort {

    /**
     * 3-way QuickSort using DNF partition.
     * O(n log n) average, O(n) for duplicate-heavy arrays.
     */
    public static void sort(int[] arr) {
        if (arr == null || arr.length <= 1) return;
        quickSort(arr, 0, arr.length - 1);
    }

    private static void quickSort(int[] arr, int lo, int hi) {
        if (lo >= hi) return;

        // DNF partition around arr[lo] as pivot
        int lt = lo;     // arr[lo..lt-1] < pivot
        int gt = hi;     // arr[gt+1..hi] > pivot
        int mid = lo;    // arr[lt..mid-1] == pivot
        int pivot = arr[lo];

        while (mid <= gt) {
            if (arr[mid] < pivot) {
                swap(arr, lt++, mid++);
            } else if (arr[mid] > pivot) {
                swap(arr, mid, gt--);
            } else {
                mid++;
            }
        }

        // Recurse only on < and > zones. The == zone is done.
        quickSort(arr, lo, lt - 1);
        quickSort(arr, gt + 1, hi);
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        // Duplicate-heavy array: 90% identical elements
        int[] arr = {5, 5, 5, 5, 5, 3, 3, 3, 7, 7, 7, 7, 5, 5, 5};
        System.out.println("Before: " + Arrays.toString(arr));
        sort(arr);
        System.out.println("After:  " + Arrays.toString(arr));

        // All identical: O(n) with 3-way, O(n^2) with standard QuickSort
        int[] allSame = {4, 4, 4, 4, 4, 4, 4, 4};
        sort(allSame);
        System.out.println("All same: " + Arrays.toString(allSame));
    }
}

Generalizing DNF to N Values — When 3 Pivots Aren't Enough

DNF is specialized for exactly 3 values. For 4 or more values, you need a generalized approach. The options are: counting sort (O(n+k) time, O(k) space), multiple DNF passes, or a bucket-based partition.

Counting sort is the simplest generalization: count occurrences of each value, then overwrite the array. It requires O(k) space and two passes. For k=4 or k=5, this is usually fine. For large k, the space cost dominates.

Multiple DNF passes: partition into 3 zones, then recursively apply DNF to each zone. This is essentially 3-way QuickSort with a fixed set of values. It works but adds complexity.

The practical recommendation: use counting sort for k <= 10. Use DNF (as 3-way QuickSort partition) for arbitrary values with expected duplicates. Use standard comparison sort for general-purpose sorting.

package io.thecodeforge.algo;

import java.util.Arrays;

public class CountingSortKValues {

    /**
     * Sorts an array of k distinct values using counting sort.
     * O(n + k) time, O(k) space.
     * Use when k is small (k <= 10) and you need a simple solution.
     */
    public static void sort(int[] arr, int k) {
        if (arr == null || arr.length <= 1) return;

        int[] count = new int[k];
        for (int val : arr) {
            count[val]++;
        }

        int idx = 0;
        for (int val = 0; val < k; val++) {
            for (int j = 0; j < count[val]; j++) {
                arr[idx++] = val;
            }
        }
    }

    public static void main(String[] args) {
        // Sort 5 values (0-4)
        int[] arr = {3, 0, 4, 1, 2, 3, 0, 1, 4, 2};
        System.out.println("Before: " + Arrays.toString(arr));
        sort(arr, 5);
        System.out.println("After:  " + Arrays.toString(arr));
    }
}

The Brute Force That Works (But You Shouldn't Ship)

Every junior writes this once. They import Arrays.sort() and call it done. O(n log n) for a problem that screams O(n). It passes the test cases. It fails the code review. Here's why: when you sort three distinct values, comparison-based sorting does way more work than you need. The algorithm doesn't know the values are bounded. It's shuffling elements around n log n times when a single pass will do. The naive approach works fine for arrays smaller than 10 elements. For production payloads — millions of records from a sensor array or a color-coded inventory system — that log factor starts bleeding latency. More importantly, sorting is a sledgehammer when you need a scalpel. You're not comparing items; you're partitioning. Know the difference.

// io.thecodeforge — dsa tutorial
// Why you don't sort three values — O(n log n) is overkill

import java.util.Arrays;

public class SortNaive {
    public static void sortColors(int[] inventory) {
        // Works. But cheap.
        Arrays.sort(inventory);
    }

    public static void main(String[] args) {
        int[] sensorData = {2, 0, 1, 2, 1, 0, 0, 1, 2};
        sortColors(sensorData);
        System.out.println(Arrays.toString(sensorData));
    }
}

The Two-Pass Crutch (and Why It Breaks In-Place Requirements)

So you avoided the sort trap. Smart. Now you do two passes: count zeros, ones, twos in pass one, then overwrite the array in pass two. This is the 'better approach' everyone regurgitates in interviews. It's O(n) time and O(1) space — looks good on paper. But look closer: you're still writing to the array twice. For cache-bound hot paths, that second pass reloads the entire array from memory. On embedded systems — think medical devices, IoT endpoints — write cycles cost power and flash wear. The real killer? It's not an in-place algorithm. You're constructing a new array conceptually by writing order. For large objects (not just integers), building the sorted sequence by overwriting might not be trivial. DNF does it in one pass, no counting, no reconstruction. The pointer strategy exists because counting is a crutch. Ditch it.

// io.thecodeforge — dsa tutorial
// Two-pass counting. Works. Not optimal.

import java.util.Arrays;

public class CountAndFill {
    public static void sortColors(int[] items) {
        int zeros = 0, ones = 0, twos = 0;
        for (int val : items) {
            if (val == 0) zeros++;
            else if (val == 1) ones++;
            else twos++;
        }
        int idx = 0;
        while (zeros-- > 0) items[idx++] = 0;
        while (ones-- > 0) items[idx++] = 1;
        while (twos-- > 0) items[idx++] = 2;
    }

    public static void main(String[] args) {
        int[] packets = {2, 0, 1, 2, 1, 0};
        sortColors(packets);
        System.out.println(Arrays.toString(packets));
    }
}

The 'Aha!' Moment: Why the Middle Pointer Never Stops

Most learners get lost on one rule: The middle pointer never advances after a swap with the high pointer. Why? Because when you swap with the low pointer, you're swapping a 0 (known good) into place — the swapped-in value is always 0 or 1. You advance both low and middle. But when you swap with the high pointer, you're pulling in garbage from the 'unknown' zone. Could be 0, 1, or 2. You can't assume it's clean. So you don't advance the middle pointer — you re-evaluate the swapped value on the next iteration. This is not pedantry. It's correctness. Skip this rule and you'll skip over unsorted values. I've debugged this exact bug in a production color-sorting pipeline for warehouse robots. The robots started binning 1s with 2s. Warehouse chaos. That single line — mid++ or not — cost an afternoon of cargo-picking downtime. Remember: swap with low = safe advance. Swap with high = re-check.

// io.thecodeforge — dsa tutorial
// Single-pass partition — the one that works in production

import java.util.Arrays;

public class DNFCorrect {
    public static void sortColors(int[] warehouse) {
        int low = 0, mid = 0, high = warehouse.length - 1;
        while (mid <= high) {
            switch (warehouse[mid]) {
                case 0:
                    swap(warehouse, low, mid);
                    low++; mid++;
                    break;
                case 1:
                    mid++;
                    break;
                case 2:
                    swap(warehouse, mid, high);
                    high--;
                    // mid does NOT advance — re-evaluate swapped value
                    break;
            }
        }
    }

    private static void swap(int[] arr, int i, int j) {
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    public static void main(String[] args) {
        int[] stock = {2, 0, 2, 1, 1, 0};
        sortColors(stock);
        System.out.println(Arrays.toString(stock));
    }
}