Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Imperative programming resit / 2 / a / 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:The loop invariant is $l\le k\le j\le 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 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)$.