Maximal initial run
= Maximal initial run
The longest nondecreasing prefix of a specified segment. For a nonempty segment $u[a..b)$, its endpoint is the first $c$ with $a<c<b$ and $u[c-1]>u[c]$, or $b$ if no such descent exists. Scanning adjacent pairs takes time proportional to the returned run length. An empty segment has an empty <maximal initial run>.