Mixed input
Input
arr = [2, 0, 2, 1, 1, 0]
Output
[0, 0, 1, 1, 2, 2]
After sorting 0s come first, then 1s, then 2s.
Full lesson preview
Sort an array containing only 0s, 1s, and 2s
Reorder an array consisting only of 0s, 1s, and 2s into non-decreasing order using the Dutch National Flag algorithm.
Python practice14 minTwo Pointers & Sliding WindowIntermediateLast updated March 26, 2026
Problem statement
Given a list containing only the integers 0, 1, and 2, sort the list in non-decreasing order without using the language's built-in sort. Your function should run in O(n) time and use O(1) additional space. You may return the array (either the same mutated list or a new list is acceptable), but do not use sort() or equivalent library sorting functions.
Task
Implement a single-pass, in-place sorting algorithm (Dutch National Flag) with O(n) time and O(1) extra space.
Examples
Input format
A single list of integers containing only 0, 1, and 2: arr
Output format
A list sorted in non-decreasing order.
Constraints
0 <= len(arr) <= 10^5. Elements are only 0, 1, or 2. Expected time: O(n), extra space: O(1).
Samples
Sample 1
Input
[1, 0, 2]
Output
[0, 1, 2]
Simple case with one of each value.