Sorted run

A contiguous nondecreasing segment of a sequence. Adjacent sorted runs can be merged in time linear in their combined lengths.

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.