Dutch National Flag (3-Way Partition)

Named after the Dutch flag's three horizontal stripes (red, white, blue), this trick sorts a list that only ever holds three distinct values — like 0s, 1s, and 2s — into their three neat groups in a single pass. Picture sorting a pile of laundry into three baskets, for whites, colors, and darks, by walking past each item exactly once, instead of picking it up over and over.

1. 1Keep three markers: 'low', the boundary for 0s; 'mid', the item you are currently looking at; and 'high', the boundary for 2s.
2. 2Look at the item at 'mid'. If it is a 0, swap it down to the 'low' boundary and move both low and mid forward. If it is a 1, it is already in the middle group, so just move mid forward.
3. 3If it is a 2, swap it out to the 'high' boundary and pull high inward. Do not move mid yet, since the item swapped in from the high end still needs checking. Stop once mid passes high.

Use it to sort data with only a small, fixed number of distinct categories — like sorting objects by three colors, classifying items as low, medium, or high, or as a splitting step inside quicksort when many items share the same value.

• ⚠Moving 'mid' forward after every swap, including swaps with 'high'. The item just pulled in from the high end has not been checked yet, so mid must stay put in that case.
• ⚠Using this approach on data with more than three distinct values. It is built specifically for exactly three categories, not general sorting.