= Solution
Let `a` be the given enclosing <array>. A <two-way array partition> needs only one scan, and does not require the pivot to occur in the <array>:
``
def partition(l: Int, r: Int, p: Int): Int = {
require(0 <= l && l <= r && r <= a.length)
var k = l
var j = l
while (j < r) {
if (a(j) < p) {
val t = a(k)
a(k) = a(j)
a(j) = t
k += 1
}
j += 1
}
k
}
``
The <loop invariant> is $l\leq k\leq j\leq r$, every entry of $a[l,k)$ is less than $p$, every entry of $a[k,j)$ is at least $p$, and the segment's <multiset> is unchanged. Entries outside $[l,r)$ are unchanged. When `a(j)<p`, swapping it into position `k` extends the low part; if `k<j`, the displaced entry was in the high part and remains there after `j` advances. If `k==j`, the self-swap is harmless. The other branch simply extends the high part. The <loop variant> is $r-j$. At exit $j=r$, so \b[the returned $k$ has the required separation property], including empty segments and arbitrarily many duplicate entries. The <time complexity> is $\Theta(r-l+1)$ and auxiliary <space complexity> is $O(1)$.
Back to article page
