1. Problem Statement

You are given an array consisting of only 0s, 1s, and 2s. Your task is to sort the array in-place so that all 0s come first, followed by all 1s, and then all 2s.

Example:

Input:
arr = [2, 0, 2, 1, 1, 0]

Output:
arr = [0, 0, 1, 1, 2, 2]

2. Why Is It Called the “Dutch National Flag Problem”?

The algorithm is called the Dutch National Flag Algorithm because it was proposed by Edsger W. Dijkstra, a renowned Dutch computer scientist, to model a problem inspired by the colors of the Dutch national flag, which consists of three distinct colors:

• Red
• White
• Blue

Dijkstra used these three colors to represent three categories or groups in an array, and he designed an efficient algorithm to sort them in a single pass — just like arranging the flag colors in the correct order.

3. Metaphorical Explanation

Imagine a collection of red, white, and blue balls in a line (unsorted). The goal is to sort them into a proper Dutch flag layout:

[ RED | WHITE | BLUE ]

Now replace:

• Red → 0
• White → 1
• Blue → 2

The algorithm groups all similar elements together in a specific order using three pointers (low, mid, high) and in-place swapping.

4. What makes it optimal?

The Dutch National Flag Algorithm is optimal because it sorts the array in a single pass, using constant space, and no nested loops or counting operations. It efficiently partitions the array into three sections using in-place swaps, and handles every element exactly once.

This approach avoids the inefficiencies of:

• Two-pass counting methods, where we count occurrences and then write values again.
• General-purpose sorting algorithms, which take more than linear time and unnecessary comparisons.

5. Algorithm Steps

We use three pointers:

• low: points to the position where the next 0 should go.
• mid: scans the array and evaluates each value.
• high: points to the position where the next 2 should go.

Initially:

• low = 0
• mid = 0
• high = n - 1

We loop while mid <= high. Inside the loop, we inspect arr[mid]:

Case 1: arr[mid] == 0

• This element belongs to the start of the array.
• We swap arr[mid] with arr[low] to move the 0 into the correct zone.
• Then we increment both low and mid because both positions now hold valid sorted values.

Case 2: arr[mid] == 1

• This element is already in the correct middle position.
• We simply increment mid and move on.

Case 3: arr[mid] == 2

• This element belongs at the end of the array.
• We swap arr[mid] with arr[high] to move the 2 into the correct zone.
• Then we decrement high, but we do not increment mid, because the swapped value at mid could be a 0, 1, or 2 — and we need to check it.

6. Why It Works: Logical Justification

• By moving 0s to the left and 2s to the right as soon as we see them, the array is progressively sorted from both ends inward.
• 1s are naturally left in the middle without needing to be moved unless surrounded by unsorted elements.
• Since each value is handled based on its class (0, 1, or 2), we avoid the need for any comparisons between elements — we only check values directly.

7. Visual Representation

We visualize the array and three pointers low, mid, and high:

Initial:  [2, 0, 2, 1, 1, 0]
          L  M           H

After 1:  [0, 0, 2, 1, 1, 2]
             L  M       H

After 2:  [0, 0, 2, 1, 1, 2]
                L  M    H

After 3:  [0, 0, 1, 1, 2, 2]
                L  M H

After 4:  [0, 0, 1, 1, 2, 2]
                   M   H

After 5:  [0, 0, 1, 1, 2, 2]
                      M>H => STOP

8. Java Implementation

public class DutchNationalFlag {
    public static void sortColors(int[] arr) {
        int low = 0, mid = 0;
        int high = arr.length - 1;

        while (mid <= high) {
            switch (arr[mid]) {
                case 0: // Swap arr[mid] and arr[low]
                    int temp0 = arr[low];
                    arr[low] = arr[mid];
                    arr[mid] = temp0;
                    low++;
                    mid++;
                    break;

                case 1: // Just move mid
                    mid++;
                    break;

                case 2: // Swap arr[mid] and arr[high]
                    int temp2 = arr[mid];
                    arr[mid] = arr[high];
                    arr[high] = temp2;
                    high--;
                    // Note: Don't move mid here!
                    break;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {2, 0, 2, 1, 1, 0};
        sortColors(arr);

        for (int num : arr) {
            System.out.print(num + " ");
        }
    }
}