Generalizing Dijkstra's Dutch National Flag Algorithm

Dijkstra's Dutch National Flag (DNF) algorithm is one of those deceptively simple ideas that becomes more interesting the deeper you look into it.

At first glance, it solves a very narrow problem: sorting an array containing only 0 , 1 , and 2 in a single linear pass. Elegant, clever, and usually treated as a specialized trick.

But hidden inside DNF is a much more general idea.

The algorithm works because it understands the structure of the value space . It knows exactly which values belong on the left, which belong on the right, and which belong in the middle.…