Run of a sequence

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

This article needs additional citations for verification. Please help by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources:  –  ·  ·  · scholar · JSTOR (April 2021) (Learn how and when to remove this template message)

In computer science, a run of a sequence is a longest non-decreasing range of the sequence. The number of runs of a sequence is the number of increasing subsequences of the sequence. This is a , and in particular measures how many sequences must be merged to sort a sequence.

Definition[]

Let ${\displaystyle X=\langle x_{1},\dots ,x_{n}\rangle }$ be a sequence. A run of ${\displaystyle X}$ is a maximal increasing sequence ${\displaystyle x_{i},x_{i+1},\dots ,x_{j-1},x_{j}}$. 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, in ${\displaystyle \langle n+1,n+2,\dots ,2n,1,2,\dots ,n\rangle }$, the two runs are ${\displaystyle n+1,\dots ,2n}$ and ${\displaystyle 1,\dots ,n}$.

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

Sorting sequences with a low number of runs[]

The function Runs is a . The natural merge sort, is -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 run can be merged 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.