Past exam of the year 1 of the computer science course of the University of Oxford / 2013 / Imperative programming / 3 / c / Solution

Reuse split and swap, but replace recursive calls with a FIFO queue of unresolved segments. Enqueue only segments of length at least two.A useful loop invariant is that the pending segments are pairwise disjoint valid array segments of length at least two; the whole array multiset equals its original value; and every inverted pair of positions lies in a single pending segment. Explicitly, if $i<j$ and $a(i)>a(j)$, some queued $[l,r)$ contains both $i$ and $j$. Thus all ordering obligations are localized to queued segments.

Initially the only possible pending segment is the whole array. One array partitioning confines all its remaining inversions to its two child segments. Its equal middle segment is ordered, the left/middle/right boundaries have the correct ordering, and segments of length at most one cannot contain an inversion. Because array partitioning only permutes the selected segment's entries, it cannot create an inversion across a boundary that previously had no inversions. This proves preservation of the loop invariant.

The loop variant is the total pending lengthProcessing one segment removes $r-l$ from $V$ and adds at most $(lt-l)+(r-gt)=(r-l)-(gt-lt)$, strictly less because $gt-lt\ge 1$. Thus $V$ is a nonnegative integer and decreases. At exit no pending segment exists, so no inversion exists:The FIFO queue itself can grow to $O(N)$ pairs. The time complexity is that of the corresponding recursive quicksort, including linear behavior on equal input. Removing recursion does not make the worst-case time complexity linear or eliminate the work storage.