Dutch national flag problem

[2] The flag of the Netherlands consists of three colors: red, white, and blue.

The solution to this problem is of interest for designing sorting algorithms; in particular, variants of the quicksort algorithm that must be robust to repeated elements may use a three-way partitioning function that groups items less than a given key (red), equal to the key (white) and greater than the key (blue).

Several solutions exist that have varying performance characteristics, tailored to sorting arrays with either small or large numbers of repeated elements.

Suppose each of the possible elements could be classified into exactly one of three categories (bottom, middle, and top).

[1] The following pseudocode for three-way partitioning which assumes zero-based array indexing was proposed by Dijkstra himself.