Given a array of elements representing colors using integers 0 (red), 1 (white), and 2 (blue), the task is to sort them in-place without using built-in sorting functions. The sorted array should group identical colors together in red-white-blue order.

Two-Pass Pointer Approach

This method processes the array in two sequential passes. The first pass moves all red elements (0) to the beginning, while the second pass positions white elements (1) immediately after the red section.

public void organizeColors(int[] colorArray) {
    int currentPos = 0;
    
    // First pass: move all red elements to front
    for (int scanIndex = 0; scanIndex < colorArray.length; scanIndex++) {
        if (colorArray[scanIndex] == 0) {
            int temp = colorArray[currentPos];
            colorArray[currentPos] = 0;
            colorArray[scanIndex] = temp;
            currentPos++;
        }
    }
    
    // Second pass: move white elements after red section
    for (int scanIndex = currentPos; scanIndex < colorArray.length; scanIndex++) {
        if (colorArray[scanIndex] == 1) {
            int temp = colorArray[currentPos];
            colorArray[currentPos] = 1;
            colorArray[scanIndex] = temp;
            currentPos++;
        }
    }
}

Single-Pass Three Pointer Method

The Dutch National Flag algorithm uses three pointers to sort the array in one traversal. The left pointer tracks the end of the red section, the right pointer marks the start of the blue section, and a current pointer scans elements.

public void arrangeColors(int[] colorArray) {
    int left = 0, right = colorArray.length - 1;
    int current = 0;
    
    while (current <= right) {
        if (colorArray[current] == 0) {
            // Swap red element to left section
            int temp = colorArray[left];
            colorArray[left] = 0;
            colorArray[current] = temp;
            left++;
            current++;
        } else if (colorArray[current] == 2) {
            // Swap blue element to right section
            int temp = colorArray[right];
            colorArray[right] = 2;
            colorArray[current] = temp;
            right--;
        } else {
            // White element remains in place
            current++;
        }
    }
}

The three-pointer approach maintains the invariant that elements before the left pointer are red, elements after the right pointer are blue, and elements between left and current are white. When encoutnering blue elements (2), the current pointer doesn't advence because the swapped element from the end requires evaluation.