Encyclopedia

Run of a sequence

Wikipedia contributorsAdapted for Fathomly · View authors

1 min read
Source updated June 10, 2024

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.

01Definition

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\leq 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 ${\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$ .

02Sorting 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.

03Long 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.

Watch videos about Run of a sequenceExplainers and documentaries on YouTube (opens in a new tab)

Sources and credits

This article is adapted from the Wikipedia article “Run of a sequence”, written by its contributors and licensed under CC BY-SA 4.0. Fathomly has changed the layout, removed citation markers, navigation and maintenance notices, and adjusted punctuation. This adapted version is shared under the same license. For references, see the original article.

Fathomly is not affiliated with or endorsed by the Wikimedia Foundation. Spotted a problem? Tell us.