Sort Colors (Arrays)

Dutch national flag — one pass, three regions

time O(n)space O(1)

Only three distinct values exist, so no comparison sort is needed — the array can partition itself. Grow three regions at once: settled 0s left of low, settled 2s right of high, and an unknown band low..high that shrinks on every look. A 0 is swapped to the front, a 2 is thrown to the back, a 1 is already home. The one rule that decides whether the code is correct: after swapping a 2 backwards, mid must NOT advance, because the value that came back from the right end has never been examined.

Details

Animated on: nums = [0,2,1,2,0,1,2,0] — sort it in place in a single pass, without counting the values first.

Problem:Sort Colors (Arrays)Medium

Dutch national flag — one pass, three regions

step 1 / 10

[0]

[1]

[2]

[3]

[4]

[5]

[6]

[7]

Three regions, not a sort. Everything left of low is a settled 0, everything right of high is a settled 2, and low..high is still unknown. low=0, mid=0 and high=7 start with the whole array unknown, so nothing is settled yet.

low=0· arr[0] = 0
mid=0· arr[0] = 0
high=7· arr[7] = 0

Pseudocode

1FUNCTION sortColors(nums)
2  low <- 0
3  mid <- 0
4  high <- LENGTH(nums) - 1
5  WHILE mid <= high
6    IF nums[mid] = 2
7      SWAP nums[mid] AND nums[high]
8      high <- high - 1
9    ELSE
10      IF nums[mid] = 0
11        SWAP nums[low] AND nums[mid]
12        low <- low + 1
13      mid <- mid + 1

← / → step · space play · Home restart

Every step in words

Show all 10 steps

Three regions, not a sort. Everything left of low is a settled 0, everything right of high is a settled 2, and low..high is still unknown. low=0, mid=0 and high=7 start with the whole array unknown, so nothing is settled yet.
nums[0]=0 is already sitting at the front of the unknown zone, so the swap is with itself and only the boundary moves: low and mid both step to 1.
nums[1]=2 belongs at the very back, so it trades places with nums[7]=0 and index 7 is settled — high shrinks to 6. mid stays at 1 on purpose: the 0 that just arrived from the unknown zone has never been looked at, and advancing here is the classic bug that strands it.
nums[1]=0 is already sitting at the front of the unknown zone, so the swap is with itself and only the boundary moves: low and mid both step to 2.
nums[2]=1 is already in its final band — 1s belong between the 0s and the 2s — so no swap is needed and only mid moves to 3. This is why the middle value costs nothing here.
nums[3]=2 belongs at the very back, so it trades places with nums[6]=2 and index 6 is settled — high shrinks to 5. mid stays at 3 on purpose: the 2 that just arrived from the unknown zone has never been looked at, and advancing here is the classic bug that strands it.
nums[3]=2 belongs at the very back, so it trades places with nums[5]=1 and index 5 is settled — high shrinks to 4. mid stays at 3 on purpose: the 1 that just arrived from the unknown zone has never been looked at, and advancing here is the classic bug that strands it.
nums[3]=1 is already in its final band — 1s belong between the 0s and the 2s — so no swap is needed and only mid moves to 4. This is why the middle value costs nothing here.
nums[4]=0 must go in front, so it swaps with nums[2]=1. Whatever low pointed at can only be a 1 — every 0 seen so far was filed left and every 2 was thrown right — so the 1 lands safely in the middle band and both low and mid advance.
mid=5 has passed high=4, so the unknown zone is empty and every cell is settled: 0, 0, 0, 1, 1, 2, 2, 2. One pass, 4 swaps, no counting array — and unlike a two-pass count-then-overwrite this never reads a cell twice.

Now solve it yourself

Watching is the first half. The second is writing it without the animation.

Solve Sort Colors (Arrays) in the editor All Arrays problems Back to roadmap