Sorting 0s, 1s and 2s in one pass

A list holds only the values 0, 1 and 2. Sort it. Do it in one pass over the list, using no extra storage.

Worked example#

[2, 0, 2, 1, 1, 0] becomes [0, 0, 1, 1, 2, 2].

Why not just sort it#

Calling the library sort is n log n and is the right answer in real code. But only three values exist, and that is a lot to know. Counting how many of each and rewriting the list is n, and needs two passes.

One pass is possible, and the idea behind it is worth having.

The idea#

Keep three regions and grow them as you walk:

[ all 0s ][ all 1s ][ not looked at yet ][ all 2s ]
           ^         ^                  ^
          low       at                 high

Everything before low is a 0. Everything from low to at is a 1. Everything after high is a 2. The stretch between at and high is what you have not seen.

Look at nums[at]:

• A 0: it belongs at the front. Swap it with nums[low], and move both low and at forward.
• A 2: it belongs at the back. Swap it with nums[high] and move high back. Do not move at, because what you just swapped in is a value you have not looked at.
• A 1: it is already where it belongs. Move at forward.

Stop when at passes high.

The one that catches people#

Not advancing at after a swap with high. It is the whole difference between a correct one-pass sort and one that leaves a stray 2 in the middle.

The reason is worth stating plainly: swapping with low brings back something already examined (a 1, by the invariant), so it is safe to step over. Swapping with high brings back something from the unexamined region, so it has to be examined.

What this is called#

The Dutch national flag problem, named by Dijkstra after the three-striped flag. It is also the partitioning step inside quicksort, which is why it turns up far more often than a question about three colours would suggest.

Constraints#

• 1 <= n <= 100000
• Every value is 0, 1 or 2