 Three-way array partitioning

Maintain consecutive regions less than a saved pivot value, equal to it, unclassified, and greater than it. Compare the first unclassified entry: move a smaller one into the lower region, advance over an equal one, or exchange a greater one with the final unclassified entry. In the last case the incoming entry still needs classification. Each step shortens the unclassified interval by one. The final equality interval is nonempty when the pivot was selected from the input; Quickselect can discard that entire interval when searching another rank. Saving the value avoids accidentally comparing against a pivot index whose contents have moved.