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

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

Sorting sequences with a low number of runs

The function [math]\displaystyle{ \mathtt{runs} }[/math] is a measure of presortedness. The natural merge sort is [math]\displaystyle{ \mathtt{runs} }[/math]-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.