= Solution
Maintain a processed prefix split into values below the pivot and values at least the pivot. The remaining suffix has not yet been classified. Here `a` and `N` are the given <array> and its length.
``
def partition(l: Int, r: Int, p: Int): Int = {
require(0 <= l && l <= r && r <= N)
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,\qquad a[l..k)<p,\qquad a[k..j)\geq p.
$$
In addition, the active segment remains a <permutation> of its original contents, and every entry outside it remains unchanged. If `a(j) < p`, swapping it with `a(k)` extends the first region; the displaced entry, when the two positions differ, already belongs in the second region. Otherwise only the second region grows. The <loop variant> is $r-j$. At termination $j=r$, so
$$
\boxed{a[l..k)<p\leq a[k..r),\qquad\text{return }k.}
$$
There are exactly $r-l$ iterations, giving $O(r-l+1)$ <time complexity> and constant <auxiliary space>.
Back to article page
