This article includes a list of general references but lacks sufficient corresponding inline citations. Please help improve this article by introducing more precise citations. (June 2021) (Learn how and when to remove this message)

This article needs more citations. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Run of a sequence" – news · newspapers · books · scholar · JSTOR (April 2021) (Learn how and when to remove this message)

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.

Let ${\displaystyle X=\langle x_{1},\dots ,x_{n}\rangle }$ be a sequence of elements from a totally ordered set. A run of ${\displaystyle X}$ is a maximal increasing sequence ${\displaystyle \langle x_{i},x_{i+1},\dots ,x_{j-1},x_{j}\rangle }$. That is, ${\displaystyle x_{i-1}>x_{i}}$ and ${\displaystyle x_{j}>x_{j+1}}$^{[clarification needed]} assuming that ${\displaystyle x_{i-1}}$ and ${\displaystyle x_{j+1}}$ exists. For example, if ${\displaystyle n}$ is a natural number, the sequence ${\displaystyle \langle n+1,n+2,\dots ,2n,1,2,\dots ,n\rangle }$ has the two runs ${\displaystyle \langle n+1,\dots ,2n\rangle }$ and ${\displaystyle \langle 1,\dots ,n\rangle }$.

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

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

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.

• 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.