= Solution
The original page permits $m=r$, but also indexes $a[m]$. The meaningful pivot-position contract is the stronger $l\leq m<r$, with $a[l..m)<a[m]$ and $a[m..r)\geq a[m]$. Implement this <two-way array partition> by reserving the last entry as pivot:
``
PROCEDURE Partition(l, r: INTEGER): INTEGER;
VAR pivot, i, j, tmp: INTEGER;
BEGIN
ASSERT(l < r);
pivot := a[r-1];
i := l; j := l;
WHILE j < r-1 DO
IF a[j] < pivot THEN
tmp := a[i]; a[i] := a[j]; a[j] := tmp;
i := i+1
END;
j := j+1
END;
tmp := a[i]; a[i] := a[r-1]; a[r-1] := tmp;
RETURN i
END Partition;
``
The <loop invariant> is
$$
l\leq i\leq j\leq r-1,\qquad
a[l..i)<\mathrm{pivot},\qquad a[i..j)\geq\mathrm{pivot},\qquad a[r-1]=\mathrm{pivot}.
$$
The segment's <multiset> is preserved and entries outside $[l,r)$ are unchanged. The unclassified part is $[j,r-1)$. A smaller entry is swapped into the left group; if $i<j$, the displaced entry belongs to the greater-or-equal group. Otherwise the entry simply joins that group. The <loop variant> is $r-1-j$.
At exit the final <swap> installs the pivot at `i`, giving
$$
\boxed{m=i\in[l,r),\quad a[l..m)<a[m]\leq a[m..r),\quad T=\Theta(r-l).}
$$
A singleton segment is handled without loop iterations. Equality belongs on the pivot's right side, as required by the printed strict left inequality.
Back to article page
