Two-way array partition

Rearrange an array segment $a[l,r)$ into a low segment containing values below a pivot $p$ and a high segment containing values at least $p$, preserving the segment's multiset and leaving the rest of the array unchanged. The pivot need not itself occur, and either resulting segment may be empty.

An in-place scan maintains indices $l\le k\le j\le r$ with $a[l,k)<p$ and $a[k,j)\ge p$. A low value at $j$ is swapped into position $k$ and advances both indices; a high value advances only $j$. The unexamined length $r-j$ is a loop variant. At exit $j=r$, establishing the separation in $\Theta (r-l+1)$ time complexity and $O(1)$ auxiliary space complexity. Equal values consistently belong to the high side.

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.