CA 08 - Sort 0s, 1s, and 2s

Problem
Sort 0s, 1s and 2s
You are given an array arr[] containing only 0s, 1s, and 2s.
Your task is to sort the array in ascending order without using any built-in sort function.
Input: [0, 1, 2, 0, 1, 2] → Output: [0, 0, 1, 1, 2, 2]

Approach

This problem can be efficiently solved using the Dutch National Flag algorithm.

We divide the array into three regions:

• 0s on the left
• 1s in the middle

• 2s on the right
  Steps:

• Use three pointers: low, mid, and high

• Traverse the array once:

  • If element is 0 → swap with low, move both pointers forward
  • If element is 1 → move mid forward
  • If element is 2 → swap with high, move high backward

This ensures sorting in a single pass without extra space.

Complexity:
Time Complexity: O(n)
Space Complexity: O(1)

def sort012(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], arr[high] = arr[high], arr[mid]
            high -= 1
    return arr
arr = [0, 1, 2, 0, 1, 2]
print(sort012(arr))