= Solution
Use <three-way array partitioning> around a saved pivot value:
``
procedure Partition(var a; l, r; var m, n)
x := a[Pivot(a,l,r)]
m := l
k := l
n := r
while k < n do
if a[k] < x then
swap(a[k], a[m])
m := m+1
k := k+1
else if a[k] > x then
n := n-1
swap(a[k], a[n])
else
k := k+1
``
Assume a total ordering on the element keys. The <loop invariant> partitions the original segment into
$$
a[l..m)<x,\quad a[m..k)=x,\quad a[k..n)\text{ unclassified},\quad a[n..r)>x,
$$
with $l\leq m\leq k\leq n\leq r$ and the segment's <multiset> unchanged. A smaller entry exchanges with the first equality position; the displaced equal entry is accounted for when both indices advance. A greater entry exchanges with the last unclassified position, so `k` must stay to inspect the incoming entry. The <loop variant> $n-k$ decreases by one in every branch.
At termination the equality interval is $[m,n)$. It is nonempty because the pivot value came from the segment and swaps preserve the bag. The stronger strict outer-region conditions therefore imply the requested overlapping inequalities $a[l..n)\leq x\leq a[m..r)$ and $l\leq m<n\leq r$. Storing the pivot value avoids following an array position whose contents may move.
\Image[/past-exam-of-the-year-1-of-the-computer-science-course-of-the-university-of-oxford/2017/imperative-three-way-partition.png]
{title=Four-region invariant for duplicate-aware array partitioning}
{description=The unclassified interval shrinks at every comparison. On completion, the equal interval remains nonempty and both outer intervals can be discarded or searched by rank.}
Back to article page
