🔵 Sort 0s, 1s and 2s (Dutch National Flag Algorithm)

Sorting an array containing only 0s, 1s, and 2s is a classic problem in Data Structures.
It is commonly solved using the Dutch National Flag Algorithm, which is highly efficient.

---

📌 Problem Statement

Given an array arr[] containing only 0, 1, and 2, sort the array in ascending order without using built-in sort.

---

🔍 Examples

Example 1:

Input:  [0, 1, 2, 0, 1, 2]
Output: [0, 0, 1, 1, 2, 2]

Example 2:

Input:  [0, 1, 1, 0, 1, 2, 1, 2, 0, 0, 0, 1]
Output: [0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 2, 2]

---

🧠 Concept

We divide the array into three regions:

• Left → all 0s
• Middle → all 1s
• Right → all 2s

We use three pointers:

• low → position for next 0
• mid → current element
• high → position for next 2

---

🔄 Approach: One-Pass (Optimal Solution)

Step-by-Step:

1. Initialize:

• low = 0
• mid = 0
• high = n - 1

1. Traverse while mid <= high:

• If arr[mid] == 0:

  • Swap arr[low] and arr[mid]
  • low++, mid++

• If arr[mid] == 1:

  • Move mid++

• If arr[mid] == 2:

  • Swap arr[mid] and arr[high]
  • high-- (do NOT increment mid here)

---

💻 Python Code

```python id="c1i8rm"
def sort_012(arr):
low = 0
mid = 0
high = len(arr) - 1

while mid <= high:
    if arr[mid] == 0:
        arr[low], arr[mid] = arr[mid], arr[low]
        low += 1
        mid += 1

    elif arr[mid] == 1:
        mid += 1

    else:  # arr[mid] == 2
        arr[mid], arr[high] = arr[high], arr[mid]
        high -= 1

return arr

Example

print(sort_012([0, 1, 2, 0, 1, 2]))

---

## 🧾 Dry Run (Step-by-Step)

For:



```id="m3z2fg"
arr = [0, 1, 2, 0, 1, 2]

Step	low	mid	high	Array
1	0	0	5	[0, 1, 2, 0, 1, 2]
2	1	1	5	[0, 1, 2, 0, 1, 2]
3	1	1	4	[0, 1, 1, 0, 1, 2]
4	1	2	4	[0, 1, 1, 0, 1, 2]
5	2	3	4	[0, 0, 1, 1, 1, 2]

Final → [0, 0, 1, 1, 2, 2]

---

⚡ Time and Space Complexity

• Time Complexity: O(n) (single traversal)
• Space Complexity: O(1) (in-place)

---

🔁 Alternative Approach (Counting Method)

```python id="6qz4ki"
def sort_012(arr):
count0 = arr.count(0)
count1 = arr.count(1)
count2 = arr.count(2)

i = 0
for _ in range(count0):
    arr[i] = 0
    i += 1
for _ in range(count1):
    arr[i] = 1
    i += 1
for _ in range(count2):
    arr[i] = 2
    i += 1

return arr

---

## 🧩 Where Is This Used?

* Partitioning problems
* QuickSort optimizations
* Interview questions

---

## 🏁 Conclusion

The **Dutch National Flag Algorithm** is the best solution for this problem because it:

* Works in **one pass**
* Uses **constant space**
* Is highly efficient