= Solution
Keep `u[0..len)` sorted, with the <coupling invariant>
$$
0\leq\mathrm{len}\leq N,\qquad \mathrm{len}=\operatorname{length}(xs),\qquad
u[0..\mathrm{len})=\operatorname{sort}(xs).
$$
The abstract <list> retains insertion order, while the concrete <array> retains its sorted <multiset>. Initially both are empty.
``
PROCEDURE Add(x: INTEGER);
VAR i: INTEGER;
BEGIN
ASSERT(len < N);
i := len;
WHILE i > 0 DO
IF u[i-1] <= x THEN EXIT END;
u[i] := u[i-1];
i := i-1
END;
u[i] := x;
len := len+1
END Add;
PROCEDURE Get(k: INTEGER): INTEGER;
BEGIN
ASSERT((0 <= k) & (k < len));
RETURN u[k]
END Get;
``
For insertion, conceptually treat index `i` as a hole. If $U$ is the old sorted prefix of length $n$, the <loop invariant> is $0\leq i\leq n$, $u[0..i)=U[0..i)$ and $u[i+1..n+1)=U[i..n)$, with every shifted value strictly greater than $x$. The <loop variant> is $i$. The exit condition gives either no left neighbour or a left neighbour at most $x$; filling the hole establishes <sortedness> and adds exactly one occurrence, preserving the <coupling invariant>.
$$
\boxed{\operatorname{get}:\Theta(1),\qquad\operatorname{add}:O(n)\text{ and worst-case }\Theta(n).}
$$
When the new entry is smaller than every old entry, all $n$ old values must move in this contiguous sorted-prefix representation. <Binary search> can reduce comparisons to locate the insertion point, but cannot remove that linear movement cost. Appending a new largest value takes constant time in this implementation.
Back to article page
