Run of a sequence explained

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,...,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} , ... , 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 , ... , 2 n, 1 , 2 , ... , n\rangle has the two runs \langle n +1 , ... , 2 n \rangle and \langle 1 , ... ,n \rangle .

Let

runs (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 runs (\langle 1 , 2 , ... , n \rangle) =0 , that is, the runs (X) =0 if, and only if, the sequence X is sorted. As another example, runs (\langle n,n -1 , ... , 1 \rangle) = n -1 and runs (\langle 2 , 1 , 4 , 3 , ... , 2 n, 2 n -1 \rangle) = n .

Sorting sequences with a low number of runs

The function

runs is a measure of presortedness. The natural merge sort is 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 . Department of Computer Science, University of New South Wales.
• Mannila . H . Measures of Presortedness and Optimal Sorting Algorithms . IEEE Trans. Comput. . 1985 . C-34 . 318–325. 10.1109/TC.1985.5009382 .