Sort Colors Two Pointer Dutch Flag in DSA Python - Execution Trace

Concept Flow - Sort Colors Two Pointer Dutch Flag

Start: Initialize pointers

↓

low=0, mid=0, high=n-1

↓

Check mid <= high?

No→Done

Yes↓

Check nums[mid

↓

Swap nums[low

↓

mid++

↓

Swap nums[mid

↓

Repeat Check mid <= high?

We use three pointers low, mid, and high to sort colors in one pass by swapping 0s to front, 2s to end, and 1s stay in middle.

Execution Sample

DSA Python

nums = [2,0,2,1,1,0]
low = 0
mid = 0
high = 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], nums[high] = nums[high], nums[mid]
        high -= 1

Sorts the list nums containing 0,1,2 using three pointers in one pass.

Execution Table

Step	Operation	low	mid	high	Array State	Pointer Changes
1	Start	0	0	5	[2,0,2,1,1,0]	Initialize pointers
2	Check nums[mid]=2	0	0	5	[2,0,2,1,1,0]	Swap nums[mid] and nums[high], high--
3	Swap nums[0]<->nums[5]	0	0	4	[0,0,2,1,1,2]	high=5->4, mid stays 0
4	Check nums[mid]=0	0	0	4	[0,0,2,1,1,2]	Swap nums[low] and nums[mid], low++, mid++
5	Swap nums[0]<->nums[0]	1	1	4	[0,0,2,1,1,2]	low=0->1, mid=0->1
6	Check nums[mid]=0	1	1	4	[0,0,2,1,1,2]	Swap nums[low] and nums[mid], low++, mid++
7	Swap nums[1]<->nums[1]	2	2	4	[0,0,2,1,1,2]	low=1->2, mid=1->2
8	Check nums[mid]=2	2	2	4	[0,0,2,1,1,2]	Swap nums[mid] and nums[high], high--
9	Swap nums[2]<->nums[4]	2	2	3	[0,0,1,1,2,2]	high=4->3, mid stays 2
10	Check nums[mid]=1	2	2	3	[0,0,1,1,2,2]	mid++
11	mid=2->3	2	3	3	[0,0,1,1,2,2]	No swap
12	Check nums[mid]=1	2	3	3	[0,0,1,1,2,2]	mid++
13	mid=3->4	2	4	3	[0,0,1,1,2,2]	No swap
14	Check mid <= high? 4 <= 3	2	4	3	[0,0,1,1,2,2]	Condition false, stop

💡 mid (4) > high (3), sorting complete

Variable Tracker

Variable	Start	After Step 3	After Step 5	After Step 7	After Step 9	After Step 11	After Step 13	Final
low	0	0	1	2	2	2	2	2
mid	0	0	1	2	2	3	4	4
high	5	4	4	4	3	3	3	3
nums	[2,0,2,1,1,0]	[0,0,2,1,1,2]	[0,0,2,1,1,2]	[0,0,2,1,1,2]	[0,0,1,1,2,2]	[0,0,1,1,2,2]	[0,0,1,1,2,2]	[0,0,1,1,2,2]

Key Moments - 3 Insights

Why do we not increment mid when swapping with high pointer?

Because after swapping with high, the new nums[mid] is unknown and must be checked again. See steps 2-3 and 8-9 where mid stays the same after swap.

Why do we increment both low and mid when swapping 0?

Because swapping 0 to front ensures that position is sorted, so we can safely move both pointers forward. See steps 4-7 where low and mid both increment.

When does the loop stop?

The loop stops when mid passes high, meaning all elements beyond high are sorted as 2s. See step 14 where mid=4 > high=3.

Visual Quiz - 3 Questions

Look at the execution table at step 9, what is the array state?

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

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

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

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

💡 Hint

Check the 'Array State' column at step 9 in the execution_table.

At which step does the mid pointer first increment without swapping?

A Step 10

B Step 2

C Step 6

D Step 4

💡 Hint

Look for steps where 'mid++' happens without swap in the 'Pointer Changes' column.

If we changed the first element from 2 to 1, what would happen at step 2?

A Swap with high pointer and decrement high

B Increment mid pointer only

C Swap with low pointer and increment low and mid

D Loop ends immediately

💡 Hint

Check the condition for nums[mid] == 1 in the code and execution_table steps.

Concept Snapshot

Sort Colors (0,1,2) using three pointers:
- low: next position for 0
- mid: current element
- high: next position for 2
Loop while mid <= high:
- If nums[mid]==0: swap with low, low++, mid++
- If nums[mid]==1: mid++
- If nums[mid]==2: swap with high, high--
One pass, in-place, O(n) time.

Full Transcript

This visualization shows how the Dutch National Flag algorithm sorts an array of 0s, 1s, and 2s using three pointers: low, mid, and high. Initially, low and mid start at the beginning, and high at the end. We check the element at mid: if it's 0, we swap it with low and move both pointers forward; if it's 1, we just move mid forward; if it's 2, we swap it with high and move high backward without moving mid, because the swapped element needs checking. This continues until mid passes high, ensuring all 0s are at front, 1s in middle, and 2s at end. The execution table tracks each step, pointer positions, and array state changes. Key moments clarify why mid doesn't always move after swapping with high and when the loop ends. The quiz tests understanding of pointer movements and array states during sorting.