Sort Colors - Dutch National Flag Algorithm

Array

Low Pointer

Next position for 0

Mid Pointer

Current element

High Pointer

Next position for 2

Red (0s)

[0, low)

White (1s)

[low, mid)

Blue (2s)

(high, end]

Click "Step" or "Play" to start the visualization

0 (Red)

1 (White)

2 (Blue)

▲ low - boundary for 0s

▲ mid - current scan

▲ high - boundary for 2s

Python Code - Dutch National Flag Algorithm

                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

Complexity Analysis

Time Complexity O(n) Space Complexity O(1)

Time Complexity: O(n)

Breakdown

mid pointer traverses array left-to-right
Each element is visited at most once by mid
Swap operations: O(1) per element
Loop terminates when mid > high

T(n) = n iterations × O(1) work = O(n)

Mathematical Intuition

The invariant partitions the array into four regions: [0, low) contains 0s, [low, mid) contains 1s, (high, n-1] contains 2s, and [mid, high] is unprocessed. Each iteration shrinks the unprocessed region by at least one element, guaranteeing termination in exactly n steps.

Key Insight

Unlike comparison-based sorting (Ω(n log n)), three-way partitioning exploits the constraint of only three distinct values to achieve linear time.

Space Complexity: O(1)

Breakdown

Three integer pointers: low, mid, high
One temporary variable for swapping
No auxiliary arrays or data structures
In-place modification of input array

S(n) = O(1) — constant extra space

Mathematical Intuition

The algorithm achieves in-place partitioning by using the boundaries themselves to encode the sorted structure. No counting array or bucket storage is needed—the input array serves as both source and destination.

Key Insight

This is a "stable-ish" in-place algorithm: while not strictly stable, it preserves relative order within each color group better than random quicksort.