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

edit

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  .

Sorting sequences with a low number of runs

edit

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.

Long runs

edit

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

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