Dutch national flag algorithm

Problem

The flag of the Netherlands consists of three colours: red, white, and blue. Given an array of three colors arranged randomly, the task is to arrange them such that:

• Elements of the same colour are adjacent.
• Their collective colour groups are in the correct order (red, white, blue).

Algorithm

The optimal solution for the problem is propsed by Edsger Dijkstra. The solution uses three pointers (red, white, blue) for each colours, and keeps four invariants:

• Everything at the left of red are red.
• From the red pointer to the left of the white pointer are white.
• From the white pointer to the blue pointer are unknown.
• Everything at the right of blue are blue.

The algorithm starts by setting pointers red and white to the first element, and blue pointer to the last element.

Its time complexity is $\mathcal{O}(n)$, where $n$ is the number of elements. Its space complexity is $\mathcal{O}(1)$, as it only needs the space for pointers.

Below is a python code of the Dutch national flag algorithm, that sorts the given array in place.

def dutch_national_flag(arr: List[int]) -> None:
    red, white, blue = 0, 0, len(arr) - 1
 
    while white <= blue:
        match arr[white]:
            case RED:
                arr[red], arr[white] = arr[white], arr[red]
                red += 1
                white += 1
            case WHITE:
                white += 1
            case BLUE:
                arr[blue], arr[white] = arr[white], arr[blue]
                blue -= 1

References

• Wikimedia Foundation. (2023, February 25). Dutch national flag problem. Wikipedia. Retrieved April 30, 2023, from https://en.wikipedia.org/wiki/Dutch_national_flag_problem
• CodeSmart. (2021, December 31). Dutch national flag algorithm. Explained with playing cards. YouTube. Retrieved April 30, 2023, from https://www.youtube.com/watch?v=9pdkbqGwUhs