Integer Sorting via Value-Space Partitioning

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 v