= Two-way array partition
= Array partitioning
{synonym}
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\leq k\leq j\leq r$ with $a[l,k)<p$ and $a[k,j)\geq 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.
Back to article page
