= Solution
Return the exclusive endpoint of the <maximal initial run>:
``
PROCEDURE Run(a, b: INTEGER): INTEGER;
VAR c: INTEGER;
BEGIN
IF a = b THEN RETURN b END;
c := a+1;
WHILE c < b DO
IF u[c-1] > u[c] THEN RETURN c END;
c := c+1
END;
RETURN c
END Run;
``
The <loop invariant> is $a<c\leq b$ and $u[a..c)$ is nondecreasing. An unsuccessful adjacent-order test extends the run by one; a strict descent at $c$ prevents any extension across it. If $c=b$, the whole segment is a run. The <loop variant> is $b-c$.
$$
\boxed{u[a..\operatorname{Run}(a,b))\text{ is the maximal initial run}.}
$$
For a run of length $s>0$, the <running time> is $\Theta(s)$, including at most one failed extension test; an empty segment takes $\Theta(1)$.
Back to article page
