Sort an Array of 0s, 1s, and 2s

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.

Understanding the Problem

We are given an array that only contains the numbers 0, 1, and 2. Our goal is to sort this array in-place so that all 0s come first, followed by all 1s, and then all 2s. This problem is also known as the Dutch National Flag problem.

Since we know the array only has 0s, 1s, and 2s, we can solve this more efficiently than using general sorting algorithms like quicksort. We’ll walk through this step-by-step using an intuitive approach designed for beginners.

Step-by-Step Approach with Example

Let’s say the input array is:

[2, 0, 2, 1, 1, 0]

We will use a three-pointer technique:

• low: Points to the position where the next 0 should go.
• mid: Points to the current element we are checking.
• high: Points to the position where the next 2 should go.

Initial State

low = 0, mid = 0, high = 5
Array: [2, 0, 2, 1, 1, 0]

Case 1: arr[mid] == 0

This value should go to the beginning. We swap arr[mid] with arr[low] and move both low and mid one step forward.

Case 2: arr[mid] == 1

1 is already in the middle section where it belongs, so we just move mid forward.

Case 3: arr[mid] == 2

We want to move 2 to the end. We swap arr[mid] with arr[high] and move high backward. But we do not move mid yet, because we need to check the new element that was swapped in.

Full Walkthrough of the Example

Let’s see how the array evolves:

1. Start: [2, 0, 2, 1, 1, 0]
2. Swap arr[0] and arr[5] → [0, 0, 2, 1, 1, 2], low = 0, mid = 0, high = 4
3. arr[0] == 0 → swap arr[0] and arr[0], move low and mid → [0, 0, 2, 1, 1, 2]
4. arr[1] == 0 → swap arr[1] and arr[1], move low and mid → [0, 0, 2, 1, 1, 2]
5. arr[2] == 2 → swap arr[2] and arr[4] → [0, 0, 1, 1, 2, 2], high = 3
6. arr[2] == 1 → just move mid → [0, 0, 1, 1, 2, 2]
7. arr[3] == 1 → just move mid → done

Final result: [0, 0, 1, 1, 2, 2]

Handling Edge Cases

• Empty array: No elements to process — the loop doesn’t run, so we return the array as-is.
• Single element: One value is already "sorted" — return it directly.
• All values are the same: For example, all 0s or all 2s — no swaps needed, array remains unchanged.

Why This Algorithm Is Efficient

Because we only go through the array once — and every swap or comparison brings us closer to the goal — this method runs in O(n) time and uses O(1) space.

It’s fast, space-efficient, and easy to implement once the logic is clear!

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.

#include <stdio.h>

void sortColors(int arr[], int n) {
    int low = 0, mid = 0, high = n - 1;
    while (mid <= high) {
        if (arr[mid] == 0) {
            int temp = arr[low];
            arr[low] = arr[mid];
            arr[mid] = temp;
            low++;
            mid++;
        } else if (arr[mid] == 1) {
            mid++;
        } else {
            int temp = arr[mid];
            arr[mid] = arr[high];
            arr[high] = temp;
            high--;
        }
    }
}

int main() {
    int arr[] = {2, 0, 2, 1, 1, 0};
    int n = sizeof(arr) / sizeof(arr[0]);
    sortColors(arr, n);
    printf("Sorted Array: ");
    for (int i = 0; i < n; i++) printf("%d ", arr[i]);
    return 0;
}

#include <iostream>
#include <vector>
using namespace std;

void sortColors(vector<int>& arr) {
    int low = 0, mid = 0, high = arr.size() - 1;
    while (mid <= high) {
        if (arr[mid] == 0)
            swap(arr[low++], arr[mid++]);
        else if (arr[mid] == 1)
            mid++;
        else
            swap(arr[mid], arr[high--]);
    }
}

int main() {
    vector<int> arr = {2, 0, 2, 1, 1, 0};
    sortColors(arr);
    cout << "Sorted Array: ";
    for (int num : arr) cout << num << " ";
    return 0;
}

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

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

public class SortColors {
    public static void sortColors(int[] arr) {
        int low = 0, mid = 0, high = arr.length - 1;
        while (mid <= high) {
            if (arr[mid] == 0) {
                int temp = arr[low];
                arr[low] = arr[mid];
                arr[mid] = temp;
                low++;
                mid++;
            } else if (arr[mid] == 1) {
                mid++;
            } else {
                int temp = arr[mid];
                arr[mid] = arr[high];
                arr[high] = temp;
                high--;
            }
        }
    }

    public static void main(String[] args) {
        int[] arr = {2, 0, 2, 1, 1, 0};
        sortColors(arr);
        System.out.print("Sorted Array: ");
        for (int num : arr) System.out.print(num + " ");
    }
}

function sortColors(arr) {
    let low = 0, mid = 0, high = arr.length - 1;
    while (mid <= high) {
        if (arr[mid] === 0) {
            [arr[low], arr[mid]] = [arr[mid], arr[low]];
            low++;
            mid++;
        } else if (arr[mid] === 1) {
            mid++;
        } else {
            [arr[mid], arr[high]] = [arr[high], arr[mid]];
            high--;
        }
    }
    return arr;
}

const arr = [2, 0, 2, 1, 1, 0];
console.log('Sorted Array:', sortColors(arr));

package main

import (
    "fmt"
)

func sortColors(arr []int) {
    low, mid, high := 0, 0, len(arr)-1
    for mid <= high {
        switch arr[mid] {
        case 0:
            arr[low], arr[mid] = arr[mid], arr[low]
            low++
            mid++
        case 1:
            mid++
        case 2:
            arr[mid], arr[high] = arr[high], arr[mid]
            high--
        }
    }
}

func main() {
    arr := []int{2, 0, 2, 1, 1, 0}
    sortColors(arr)
    fmt.Print("Sorted Array: ")
    for _, v := range arr {
        fmt.Print(v, " ")
    }
}

fn sort_colors(arr: &mut Vec<i32>) {
    let (mut low, mut mid, mut high) = (0, 0, arr.len() - 1);
    while mid <= high {
        match arr[mid] {
            0 => {
                arr.swap(low, mid);
                low += 1;
                mid += 1;
            },
            1 => {
                mid += 1;
            },
            _ => {
                arr.swap(mid, high);
                if high == 0 { break; }
                high -= 1;
            }
        }
    }
}

fn main() {
    let mut arr = vec![2, 0, 2, 1, 1, 0];
    sort_colors(&mut arr);
    print!("Sorted Array: ");
    for num in arr {
        print!("{} ", num);
    }
}

fun sortColors(arr: IntArray) {
    var low = 0
    var mid = 0
    var high = arr.size - 1
    while (mid <= high) {
        when (arr[mid]) {
            0 -> {
                arr[low] = arr[mid].also { arr[mid] = arr[low] }
                low++
                mid++
            }
            1 -> mid++
            2 -> {
                arr[mid] = arr[high].also { arr[high] = arr[mid] }
                high--
            }
        }
    }
}

fun main() {
    val arr = intArrayOf(2, 0, 2, 1, 1, 0)
    sortColors(arr)
    print("Sorted Array: ")
    for (num in arr) print("$num ")
}

func sortColors(_ arr: inout [Int]) {
    var low = 0, mid = 0, high = arr.count - 1
    while mid <= high {
        switch arr[mid] {
        case 0:
            arr.swapAt(low, mid)
            low += 1
            mid += 1
        case 1:
            mid += 1
        case 2:
            arr.swapAt(mid, high)
            high -= 1
        default:
            break
        }
    }
}

var arr = [2, 0, 2, 1, 1, 0]
sortColors(&arr)
print("Sorted Array:", terminator: " ")
for num in arr {
    print(num, terminator: " ")
}

function sortColors(arr: number[]): number[] {
    let low = 0, mid = 0, high = arr.length - 1;
    while (mid <= high) {
        if (arr[mid] === 0) {
            [arr[low], arr[mid]] = [arr[mid], arr[low]];
            low++;
            mid++;
        } else if (arr[mid] === 1) {
            mid++;
        } else {
            [arr[mid], arr[high]] = [arr[high], arr[mid]];
            high--;
        }
    }
    return arr;
}

const arr: number[] = [2, 0, 2, 1, 1, 0];
console.log("Sorted Array:", sortColors(arr));

Time complexity

Space complexity

O(1)

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