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 $X=⟨x_1,\dots ,x_n⟩$ be a sequence of elements from a totally ordered set. A run of $X$ is a maximal increasing sequence $⟨x_i,x_{i+1},\dots ,x_{j-1},x_j⟩$. That is, $x_{i-1}>x_i$ and $x_j>x_{j+1}$ assuming that $x_{i-1}$ and $x_{j+1}$ exists. For example, if $n$ is a natural number, the sequence $⟨n+1,n+2,\dots ,2n,1,2,\dots ,n⟩$ has the two runs $⟨n+1,\dots ,2n⟩$ and $⟨1,\dots ,n⟩$.

Let $\mathtt{r}\mathtt{u}\mathtt{n}\mathtt{s}(X)$ be defined as the number of positions $i$ such that $1\le i<n$ and $x_{i+1}<x_i$. It is equivalently defined as the number of runs of $X$ minus one. This definition ensure that $\mathtt{r}\mathtt{u}\mathtt{n}\mathtt{s}(⟨1,2,\dots ,n⟩)=0$, that is, the $\mathtt{r}\mathtt{u}\mathtt{n}\mathtt{s}(X)=0$ if, and only if, the sequence $X$ is sorted. As another example, $\mathtt{r}\mathtt{u}\mathtt{n}\mathtt{s}(⟨n,n-1,\dots ,1⟩)=n-1$ and $\mathtt{r}\mathtt{u}\mathtt{n}\mathtt{s}(⟨2,1,4,3,\dots ,2n,2n-1⟩)=n$.

Sorting sequences with a low number of runs

The function $\mathtt{r}\mathtt{u}\mathtt{n}\mathtt{s}$ is a measure of presortedness. The natural merge sort is $\mathtt{r}\mathtt{u}\mathtt{n}\mathtt{s}$-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.

References

• Powers, David M. W.; McMahon, Graham B. (1983). DCS Technical Report 8313 (Report). Department of Computer Science, University of New South Wales. 
• Mannila, H (1985). "Measures of Presortedness and Optimal Sorting Algorithms". IEEE Trans. Comput. (C-34): 318–325. doi:10.1109/TC.1985.5009382.