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 , … , x n ⟩ {\displaystyle X=\langle x_{1},\dots ,x_{n}\rangle } be a sequence of elements from a totally ordered set. A run of X {\displaystyle X} is a maximal increasing sequence ⟨ x i , x i + 1 , … , x j − 1 , x j ⟩ {\displaystyle \langle x_{i},x_{i+1},\dots ,x_{j-1},x_{j}\rangle } . That is, x i − 1 > x i {\displaystyle x_{i-1}>x_{i}} and x j > x j + 1 {\displaystyle x_{j}>x_{j+1}} assuming that x i − 1 {\displaystyle x_{i-1}} and x j + 1 {\displaystyle x_{j+1}} exists. For example, if n {\displaystyle n} is a natural number, the sequence ⟨ n + 1 , n + 2 , … , 2 n , 1 , 2 , … , n ⟩ {\displaystyle \langle n+1,n+2,\dots ,2n,1,2,\dots ,n\rangle } has the two runs ⟨ n + 1 , … , 2 n ⟩ {\displaystyle \langle n+1,\dots ,2n\rangle } and ⟨ 1 , … , n ⟩ {\displaystyle \langle 1,\dots ,n\rangle } . Let r u n s ( X ) {\displaystyle {\mathtt {runs}}(X)} be defined as the number of positions i {\displaystyle i} such that 1 ≤ i < n {\displaystyle 1\leq i<n} and x i + 1 < x i {\displaystyle x_{i+1}<x_{i}} . It is equivalently defined as the number of runs of X {\displaystyle X} minus one. This definition ensure that r u n s ( ⟨ 1 , 2 , … , n ⟩ ) = 0 {\displaystyle {\mathtt {runs}}(\langle 1,2,\dots ,n\rangle )=0} , that is, the r u n s ( X ) = 0 {\displaystyle {\mathtt {runs}}(X)=0} if, and only if, the sequence X {\displaystyle X} is sorted. As another example, r u n s ( ⟨ n , n − 1 , … , 1 ⟩ ) = n − 1 {\displaystyle {\mathtt {runs}}(\langle n,n-1,\dots ,1\rangle )=n-1} and r u n s ( ⟨ 2 , 1 , 4 , 3 , … , 2 n , 2 n − 1 ⟩ ) = n {\displaystyle {\mathtt {runs}}(\langle 2,1,4,3,\dots ,2n,2n-1\rangle )=n} .
Sorting sequences with a low number of runs The function r u n s {\displaystyle {\mathtt {runs}}} is a measure of presortedness. The natural merge sort is r u n s {\displaystyle {\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 Powers, David M. W.; McMahon, Graham B. (1983). "A compendium of interesting prolog programs". 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.
