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.