Dutch National Flag (3-Way Partitioning)
Sort an array containing only 0s, 1s, and 2s in a single pass with O(1) space. Proposed by Edsger Dijkstra and named after the Dutch flag's three colors, this algorithm demonstrates elegant three-way partitioning using three pointers. It's a generalization of the partitioning step in quicksort and is optimal for this problem. Used in quicksort optimizations and k-way partitioning.
Visualization
Interactive visualization for Dutch National Flag (3-Way Partitioning)
Dutch National Flag (3-Way Partitioning)
Array (0=Red, 1=White, 2=Blue):
• Time: O(n) - single pass
• Space: O(1) - in-place
• Three-way partitioning algorithm
Interactive visualization with step-by-step execution
Implementation
1function sortColors(nums: number[]): void {
2 let low = 0, mid = 0, high = nums.length - 1;
3
4 while (mid <= high) {
5 if (nums[mid] === 0) {
6 [nums[low], nums[mid]] = [nums[mid], nums[low]];
7 low++;
8 mid++;
9 } else if (nums[mid] === 1) {
10 mid++;
11 } else {
12 [nums[mid], nums[high]] = [nums[high], nums[mid]];
13 high--;
14 }
15 }
16}Deep Dive
Theoretical Foundation
Dutch National Flag uses three pointers (low, mid, high) to maintain four regions: [0...low-1] contains 0s, [low...mid-1] contains 1s, [mid...high] is unexplored, [high+1...n-1] contains 2s. Process the unexplored region by examining arr[mid]: if 0, swap with low and advance both low and mid; if 1, just advance mid; if 2, swap with high and decrement high only (don't advance mid since swapped element needs examination). Time: O(n) single pass. Space: O(1). Generalizes to k-way partitioning for quicksort with repeated elements.
Complexity
Time
O(n)
O(n)
O(n)
Space
O(1)
Applications
Industry Use
Quicksort optimization (3-way partitioning)
Color sorting in image processing
Priority queue with three levels
Data classification into three categories
Traffic light state sorting
Ternary search tree construction
Use Cases
Related Algorithms
Quicksort
A highly efficient, in-place sorting algorithm that uses divide-and-conquer strategy. Invented by Tony Hoare in 1959, it remains one of the most widely used sorting algorithms due to its excellent average-case performance and cache efficiency.
Merge Sort
A stable, divide-and-conquer sorting algorithm with guaranteed O(n log n) performance.
Bubble Sort
Bubble Sort is the simplest sorting algorithm that works by repeatedly swapping adjacent elements if they are in the wrong order. This process is repeated until the entire array is sorted. Named for the way larger elements 'bubble' to the top (end) of the array.
Insertion Sort
Insertion Sort is a simple, intuitive sorting algorithm that builds the final sorted array one element at a time. It works similarly to how people sort playing cards in their hands - picking each card and inserting it into its correct position among the already sorted cards. Despite its O(n²) time complexity, Insertion Sort is efficient for small datasets and nearly sorted arrays, making it practical for real-world applications.