= Solution
Reuse `split` and `swap`, but replace recursive calls with a <FIFO queue> of unresolved segments. Enqueue only segments of length at least two.
``
def quicksortLoop(): Unit = {
val work = scala.collection.mutable.Queue[(Int, Int)]()
if (a.length > 1) work.enqueue((0, a.length))
while (!work.isEmpty) {
val (l, r) = work.dequeue()
val (lt, gt) = split(l, r)
if (lt - l > 1) work.enqueue((l, lt))
if (r - gt > 1) work.enqueue((gt, r))
}
}
``
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 length
$$
V=\sum_{(l,r)\text{ in work}}(r-l).
$$
Processing one segment removes $r-l$ from $V$ and adds at most $(lt-l)+(r-gt)=(r-l)-(gt-lt)$, strictly less because $gt-lt\geq1$. Thus $V$ is a nonnegative <integer> and decreases. At exit no pending segment exists, so no inversion exists:
$$
\boxed{\text{The original array is sorted in place and preserves every multiplicity}.}
$$
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.
Back to article page
