Sort an Array of 0s, 1s, and 2s Using Dutch National Flag Algorithm

Contents

ProblemExamplesVisualizationSolutionAlgorithmCodeTimeSpace

Problem Statement❯

You are given an array consisting of only the numbers 0, 1, and 2. Your task is to sort the array in-place so that all 0s come first, then all 1s, followed by all 2s.

This problem must be solved without using any sorting function and in a way that is both time and space efficient. You should not use extra space for counting or storing elements separately.

Return the same array after sorting.

Examples❯

Input Array Sorted Output Description
[0, 2, 1, 2, 0] [0, 0, 1, 2, 2] Mixed 0s, 1s, 2s in random order
[2, 2, 1, 1, 0, 0] [0, 0, 1, 1, 2, 2] Completely reversed input
[0, 0, 0] [0, 0, 0] All elements are the same (0s)
[1, 1, 1, 1] [1, 1, 1, 1] All 1s – already sorted
[2, 2, 2] [2, 2, 2] All elements are 2s
[0, 1, 2] [0, 1, 2] Already sorted input
[1, 0, 2] [0, 1, 2] Just one swap needed
[] [] Empty input – nothing to sort
[2] [2] Single element array – valid and sorted
[2, 0] [0, 2] Only two elements in reverse

Visualization Player

Solution❯

The task is to sort an array that contains only 0s, 1s, and 2s — in that specific order. Instead of using a general-purpose sorting algorithm (like quicksort or mergesort), we use an optimized strategy known as the Dutch National Flag algorithm.

Why This Is Special

We don’t need to compare numbers in a traditional way because we already know the exact values we’re dealing with: just 0, 1, and 2. So, we can design a solution that finishes in one pass and doesn’t need extra space.

Understanding the Three-Pointer Approach

We use three pointers:

  • low → to track where the next 0 should go
  • mid → current index being checked
  • high → to track where the next 2 should go

We start with all three pointers at their respective ends and move mid through the array.

Case 1: Element is 0

This means we want to bring it to the front. So, we swap arr[mid] with arr[low]. Then we move both low and mid one step ahead.

Case 2: Element is 1

This is already in the middle section, so we do nothing — just move mid forward.

Case 3: Element is 2

We want to push this to the end. So, we swap arr[mid] with arr[high], and only move high backward. We do not move mid because the element swapped in from the end hasn’t been checked yet.

Handling Edge Cases

  • Empty array: The loop never runs, so we return the array as is.
  • All elements are the same: Like all 0s or all 2s – array is already sorted, nothing changes.
  • Single element: One item is always sorted by itself.

This algorithm ensures that we cover every case and do it efficiently in O(n) time and O(1) space.

Algorithm Steps❯

  1. Given an array arr consisting only of 0s, 1s, and 2s.
  2. Initialize three pointers: low = 0, mid = 0, and high = n - 1.
  3. Traverse the array with mid pointer until it exceeds high:
  4. → If arr[mid] == 0, swap arr[low] and arr[mid], increment both low and mid.
  5. → If arr[mid] == 1, just move mid one step ahead.
  6. → If arr[mid] == 2, swap arr[mid] and arr[high], and decrement high.
  7. Continue until the array is sorted.

Code

Python
JavaScript
Java
C++
C
def sort_colors(arr):
    low, mid, high = 0, 0, 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

# Sample Input
arr = [2, 0, 2, 1, 1, 0]
print("Sorted Array:", sort_colors(arr))

Time Complexity

CaseTime ComplexityExplanation
Best CaseO(n)In all cases, the array is traversed only once from start to end using the mid pointer.
Average CaseO(n)Each element is visited at most once, making the number of operations directly proportional to the array size.
Worst CaseO(n)Even in the worst distribution (e.g., alternating 0s and 2s), the algorithm completes in linear time as each element is handled in a single pass.

Space Complexity

O(1)

Explanation: The algorithm uses only constant extra space with three pointers (low, mid, high), and all operations are done in-place.