Dutch National Flag Algorithm
Sort an array of 0s, 1s, and 2s in a single pass (O(n)).
Ready to sort colors.
Ready
Speed
Pseudocode
1function sort012(arr)
2 low = 0, mid = 0, high = n-1
3 while mid <= high
4 if arr[mid] == 0:
5 swap(low, mid)
6 low++, mid++
7 else if arr[mid] == 1:
8 mid++
9 else: // arr[mid] == 2
10 swap(mid, high)
11 high--
Time Complexity
One PassO(n)
Strategy:
Maintain three regions:
- 0s: [0 ... low-1]
- 1s: [low ... high]
- 2s: [high+1 ... n]