In computer science, a run of a sequence is a non-decreasing range of the sequence that cannot be extended. The "number of runs" of a sequence is the number of increasing subsequences of the sequence. This is a measure of presortedness, and in particular measures how many subsequences must be merged to sort a sequence.
Definition.
Let formula_1 be a sequence of elements from a totally ordered set. A run of formula_2 is a maximal increasing sequence formula_3. That is, formula_4 and formula_5 assuming that formula_6 and formula_7 exists. For example, if formula_8 is a natural number, the sequence formula_9 has the two runs formula_10 and formula_11.
Let formula_12 be defined as the number of positions formula_13 such that formula_14 and formula_15. It is equivalently defined as the number of runs of formula_2 minus one. This definition ensure that formula_17, that is, the formula_18 if, and only if, the sequence formula_2 is sorted. As another example, formula_20 and formula_21.
Sorting sequences with a low number of runs.
The function formula_22 is a measure of presortedness. The natural merge sort is formula_22-optimal. That is, if it is known that a sequence has a low number of runs, it can be efficiently sorted using the natural merge sort.
Long runs.
A long run is defined similarly to a run, except that the sequence can be either non-decreasing or non-increasing. The number of long runs is not a measure of presortedness. A sequence with a small number of long runs can be sorted efficiently by first reversing the decreasing runs and then using a natural merge sort.