Run of a sequence

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_{i+1},\dots, x_{j-1},x_j \rangle. 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 \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{runs}(X) be defined as the number of positions i such that 1\le i and x_{i+1}. It is equivalently defined as the number of runs of X minus one. This definition ensure that \mathtt{runs}(\langle 1,2,\dots, n \rangle)=0, that is, the \mathtt{runs}(X)=0 if, and only if, the sequence X is sorted. As another example, \mathtt{runs}(\langle n,n-1,\dots,1 \rangle)=n-1 and \mathtt{runs}(\langle 2,1,4,3,\dots, 2n,2n-1\rangle)=n. ==Sorting sequences with a low number of runs==

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