Dutch National Flag problem - Sort 0, 1, 2 in an array

As seen in the image above, the Dutch National Flag has three colors:
- Red at the top
- White in the middle
- Blue at the bottom
Edsger Dijkstra proposed a problem where red, blue, and white balls are given in random order. The task is to arrange them or sort them in the order of the colors in the Dutch national flag. That is the balls of the same color are to be placed together. This task is to be executed in O(n)
time complexity and without taking any extra space that is in constant space O(1)
.
Here, we will represent the balls as:
- red ball as 0
- white ball as 1
- blue ball as 2
We will consider these balls as numbers given in an array in random order. Let's see how we can solve this problem:
We have an input array that contains the numbers(balls) 0s, 1s, and 2s only in random order. The length of the array can vary but it should contain just these three numbers that are 0, 1, and 2. Our task is to sort the input array in ascending order. Let's see the input and output before moving towards the approach:
- Sorting
- Simple Counting
- Dutch National Flag Algorithm
Method 1: Sorting - O(nlogn)
O(nlogn)
.Method 2: Simple counting - O(n)
O(n)
.Method 3: Dutch National Flag Algorithm
low
, mid
, and high
. Initially, we point the low
and mid
pointers to the start that is the first element of the input array, and the high
pointer to the end that is the last element of the input array. 
arr[0]
to arr[low-1]
will be 0s and all the numbers from arr[high+1]
to arr[n-1]
will be 2s and arr[low]
to arr[mid-1]
will be 1sarr[0] to arr[low-1] ----------0arr[high+1] to arr[n-1]------2arr[low] to arr[mid-1]--------1
low
will be 0 and all the numbers to the right of high
will be 1. How to achieve this? we will traverse the input array until mid<=high
. We will check three conditions that is when arr[mid]==0
, arr[mid]==1
, and arr[mid]==2
. See the piece of code below:while mid <= high:
if arr[mid] == 0:
arr[low], arr[mid] = arr[mid], arr[low]
low = low + 1
mid = mid + 1
elif arr[mid] == 1:
mid = mid + 1
else:
arr[mid], arr[high] = arr[high], arr[mid]
high = high - 1
The above piece of code can be described as:
if arr[mid] == 0:
swap the elements at low and mid
increment low
increment mid
elif arr[mid] == 1:
increment mid
else:
swap the elements at mid and high
decrement high

mid>high
, the while
loop stops, and as said earlier, all 0s are to the left of the low
and all 1s are to the right of the high
.def dutchsort(arr, n):
low = 0
high = n - 1
mid = 0
while mid <= high:
if arr[mid] == 0:
arr[low], arr[mid] = arr[mid], arr[low]
low = low + 1
mid = mid + 1
elif arr[mid] == 1:
mid = mid + 1
else:
arr[mid], arr[high] = arr[high], arr[mid]
high = high - 1
return arr
# Driver Program
arr = [0, 1, 2, 0, 1, 2]
n = len(arr)
arr = dutchsort(arr, n)
print(arr)
[0, 0, 1, 1, 2, 2]