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

Let $\mathtt(X)$ be defined as the number of positions $i$ such that 1\le i and x_. It is equivalently defined as the number of runs of $X$ minus one. This definition ensure that $\mathtt(\langle 1,2,\dots, n \rangle)=0$, that is, the $\mathtt(X)=0$ if, and only if, the sequence $X$ is sorted. As another example, $\mathtt(\langle n,n-1,\dots,1 \rangle)=n-1$ and $\mathtt(\langle 2,1,4,3,\dots, 2n,2n-1\rangle)=n$.

Sorting sequences with a low number of runs

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

*
*{{cite journal , last1=Mannila , first1=H , title=Measures of Presortedness and Optimal Sorting Algorithms , journal=IEEE Trans. Comput. , date=1985 , issue=C-34 , pages=318–325

Sorting algorithms