The Dutch National Flag Algorithm Explained

October 16, 2025 | Algorithms

The Dutch National Flag Algorithm is a classic algorithm introduced by Edsger W. Dijkstra.
It’s used to sort an array with three distinct elements — typically referred to as red, white, and blue (or simply 0, 1, and 2).

The goal is to rearrange the array so that all 0s come first, followed by 1s, and then 2s — in one pass and without extra memory.

The Idea

Imagine you have an array containing three types of elements:
[2, 0, 1, 2, 1, 0, 0, 2]

The algorithm maintains three pointers:

• low → marks the boundary for 0s
• mid → the current element being examined
• high → marks the boundary for 2s

Algorithm steps:

1. Initialize:

• low = 0
• mid = 0
• high = array.length - 1

2. While mid <= high:

• If the element is 0, swap it with arr[low], then increment both low and mid.
• If the element is 1, just move mid forward.
• If the element is 2, swap it with arr[high] and decrement high.

This ensures that:

• All 0s are before low
• All 1s are between low and mid
• All 2s are after high

Implementation in JavaScript

function dutchNationalFlag(arr) {
let low = 0;
let mid = 0;
let high = arr.length - 1;

while (mid <= high) {
 if (arr[mid] === 0) {
   [arr[low], arr[mid]] = [arr[mid], arr[low]];
   low++;
   mid++;
 } else if (arr[mid] === 1) {
   mid++;
 } else {
   [arr[mid], arr[high]] = [arr[high], arr[mid]];
   high--;
 }
}

return arr;
}

// Example usage
const colors = [2, 0, 2, 1, 1, 0];
console.log(dutchNationalFlag(colors));

// Expected Output:
// [0, 0, 1, 1, 2, 2]

Why It Works

The algorithm ensures partitioning of the array into three sections in a single traversal:

• [0 ... low-1] → All 0s
• [low ... mid-1] → All 1s
• [high+1 ... end] → All 2s

It’s a simple yet powerful application of the three-way partitioning concept.

Time and Space Complexity

Common Use Cases

• Sorting arrays of 0s, 1s, and 2s
• Categorizing elements into three groups (e.g., low, medium, high)
• Simplifying partitioning logic in quicksort