Past exam of the year 1 of the computer science course of the University of Oxford / 2019 / Imperative programming / 2 / b / Solution

Set aside the selected pivot at the end, array partitioning the other entries, then move the pivot to the separation index:The loop invariant is $l\le p\le j\le r-1$, $a[l,p)<x$, $a[p,j)\ge x$, and $a(r-1)=x$. The segment's multiset is unchanged and all entries outside it are unchanged. A low entry is swapped into the low segment; a high entry simply extends the high segment. The loop variant is $r-1-j$. At exit, exchanging the reserved pivot with a(p) gives $a[l,p)<x$, $a(p)=x$, and $a[p+1,r)\ge x$. The displaced value at the old pivot position was already at least $x$. Length one is handled by self-swaps and an empty loop. Duplicate pivot values belong to the high side. This costs $\Theta (r-l)$ time and $O(1)$ auxiliary space.