This article includes a list of general
references, but it lacks sufficient corresponding
inline citations. (June 2021) |
This article needs additional citations for
verification. (April 2021) |
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 be a sequence of elements from a totally ordered set. A run of is a maximal increasing sequence . That is, and [ clarification needed] assuming that and exists. For example, if is a natural number, the sequence has the two runs and .
Let be defined as the number of positions such that and . It is equivalently defined as the number of runs of minus one. This definition ensure that , that is, the if, and only if, the sequence is sorted. As another example, and .
The function is a measure of presortedness. 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.
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.
This article includes a list of general
references, but it lacks sufficient corresponding
inline citations. (June 2021) |
This article needs additional citations for
verification. (April 2021) |
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 be a sequence of elements from a totally ordered set. A run of is a maximal increasing sequence . That is, and [ clarification needed] assuming that and exists. For example, if is a natural number, the sequence has the two runs and .
Let be defined as the number of positions such that and . It is equivalently defined as the number of runs of minus one. This definition ensure that , that is, the if, and only if, the sequence is sorted. As another example, and .
The function is a measure of presortedness. 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.
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.