Run of a sequence

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 be a sequence of elements from a totally ordered set. A run of is a maximal increasing sequence. That is, and assuming that and exists. For example, if is a natural number, the sequence has the two runs and.
Let be defined as the number of positions such that and. It is equivalently defined as the number of runs of minus one. This definition ensure that, that is, the if, and only if, the sequence is sorted. As another example, and.

Sorting sequences with a low number of runs

The function is a measure of presortedness. The natural merge sort is -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.