Three way partitioning
The Dutch national flag problem sorts an array of three distinct categories, classically low, middle, and high values, into three contiguous blocks. The elegant solution uses three pointers and a single pass with constant extra memory.
The three pointers
You maintain a low pointer at the end of the low block, a high pointer at the start of the high block, and a current scanner moving through the unclassified middle:
- See a low value: swap it down to the low region and advance both low and current.
- See a middle value: leave it and advance current.
- See a high value: swap it up to the high region and advance high only, without advancing current, since the swapped in value is unexamined.
The subtle pointer rule
The one tricky case is the high swap. After swapping with the high region you do not advance the current pointer, because the value you just pulled in from the high side has not yet been classified. Advancing it would skip an unexamined element.
Key idea
Three pointers partition an array into low, middle, and high blocks in one pass, with the rule that a high swap does not advance the scanner because the incoming value is still unclassified.