Sort 0s, 1s and 2s

Introduction

Given an array containing only 0s, 1s, and 2s, the task is to sort it in ascending order without using any built-in sorting function.

This is a famous problem known as the Dutch National Flag Algorithm, and it is very important for interviews.

Problem Statement

Given an array arr[] consisting only of 0, 1, and 2,
sort the array in ascending order in one pass using constant space.

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]

Intuition

We divide the array into 3 regions:

• Left -> all 0s
• Middle -> all 1s
• Right -> all 2s

We use 3 pointers to maintain these regions.

Optimized Approach (Dutch National Flag Algorithm)

We use three pointers:

• low -> for placing 0s
• mid -> current element
• high -> for placing 2s

Algorithm Steps

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:

  • mid++

• If arr[mid] == 2:

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

Code (Python)

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

Step-by-Step Idea

For [0, 1, 2, 0, 1, 2]:

• Move all 0s to left
• Move all 2s to right
• 1s automatically stay in middle

Complexity Analysis

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

Conclusion

The Dutch National Flag algorithm is an elegant and efficient way to sort arrays with limited values.
It is widely used in interviews and demonstrates strong problem-solving skills.