Past exam of the year 1 of the computer science course of the University of Oxford / 2015 / Imperative programming (resit) / 4 / c / Solution

The original page permits $m=r$, but also indexes $a[m]$. The meaningful pivot-position contract is the stronger $l\le m<r$, with $a[l..m)<a[m]$ and $a[m..r)\ge a[m]$. Implement this two-way array partition by reserving the last entry as pivot:The loop invariant isThe 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, givingA singleton segment is handled without loop iterations. Equality belongs on the pivot's right side, as required by the printed strict left inequality.