How to Sort Colors (Dutch National Flag) in Python

In-place sorting of a list of 0s, 1s, and 2s using the Dutch National Flag algorithm with O(n) time and O(1) space.

Medium Python 3.9+ Aug 9, 2026 Algorithms & data structures 14 views 0 copies

algorithm sorting two-pointers dutch-national-flag in-place

Python code

18 lines
Python 3.9+
Run it 
def sort_colors(nums):
    low, mid, high = 0, 0, len(nums) - 1

    while mid <= high:
        if nums[mid] == 0:
            nums[low], nums[mid] = nums[mid], nums[low]
            low += 1
            mid += 1
        elif nums[mid] == 1:
            mid += 1
        else:  # nums[mid] == 2
            nums[mid], nums[high] = nums[high], nums[mid]
            high -= 1

if __name__ == "__main__":
    colors = [2, 0, 2, 1, 1, 0]
    sort_colors(colors)
    print(colors)

Output

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

How it works

This solution uses three pointers: low, mid, and high to partition the array into three regions. Initially, low and mid point to the start, and high to the end. The algorithm sweeps mid from left to right, swapping elements to their correct region: 0s go to the left (before low), 1s stay in the middle, and 2s go to the right (after high). When a 0 is found, it is swapped with the element at low, and both low and mid advance; when a 2 is found, it is swapped with the element at high, and high decreases without moving mid because the swapped element needs to be examined. The loop continues until mid passes high. This is a single-pass algorithm that sorts the list in-place without extra memory.

Common mistakes

  • Incrementing `mid` without rechecking the swapped value when a 2 is moved, causing some 0s or 1s to be skipped.
  • Using a counting sort approach which requires extra memory and loses the in-place property.
  • Off-by-one errors in the loop condition (should be `mid <= high`, not `<`).

Variations

  1. Use a counting-based approach: count zeros, ones, and twos, then overwrite the original list with repeated values — this is O(n) but not in-place.
  2. Use Python's built-in `list.sort()` for simplicity, but it does not demonstrate the algorithm's efficiency and is not a single-pass solution.

Real-world use cases

  • Sorting a list of priority levels (e.g., low, medium, high) in a task scheduler without extra memory.
  • Partitioning an array of three possible states (e.g., red, green, blue) in a computer graphics pipeline.
  • Implementing a three-way quicksort partition for efficient sorting of arrays with many duplicate keys.

Sponsored

Run this sample

Open the browser IDE to tweak the example and see results without installing anything.

Open editor

More from Algorithms & data structures

Keep learning

Related tutorials and quizzes for this topic.

Tutorials

Quizzes