Measure of Presortedness: History
Please note this is an old version of this entry, which may differ significantly from the current revision.
Contributor:

In computer science, a measure of presortedness of a sequence represents how much work is required to sort the sequence. If the sequence is pre-sorted, sorting the sequence entirely require little work, hence it is expected to have a small measure of presortedness. In particular, the measure of a sorted sequence is 0. Some sorting algorithms are more efficient on pre-sorted list, as they can use this pre-work into account to avoid duplicate work. The measure of presortedness allows to formalize the notion that an algorithm is optimal for a certain measure.

• sorting algorithms
• presortedness
• sorting

## 1. Definition

Let $\displaystyle{ \mathbb N^{*} }$ represents finite sequence of natural numbers. Let $\displaystyle{ m:\mathbb N^*\to\mathbb N }$ a function sending sequence of numbers to non-negative numbers. This function is said to be a measure of presortedness if it satisfies the following axioms:

• if $\displaystyle{ X=\langle x_1,\dots,x_n\rangle }$ is in ascending order, then $\displaystyle{ m(X)=0 }$, that is, the measure of presortedness of sorted sequences is 0.
• let $\displaystyle{ X=\langle x_1,\dots,x_n\rangle }$ and $\displaystyle{ Y=\langle y_1,\dots,y_n\rangle }$. If $\displaystyle{ x_i\lt x_j }$ iff $\displaystyle{ y_i\lt y_j }$, then $\displaystyle{ m(X)=m(Y) }$. That is, the measure do not depends on the actual numbers in the sequence, but only on their order compared to other elements of the sequences.
• If $\displaystyle{ Y }$ is a subsequence of $\displaystyle{ X }$ then $\displaystyle{ m(Y)\le m(X) }$, that is, $\displaystyle{ m }$ is monotonic for the subsequence relation
• let $\displaystyle{ X=\langle x_1,\dots,x_n\rangle }$ and $\displaystyle{ Y=\langle y_1,\dots,y_n\rangle }$. If for each $\displaystyle{ i,j }$, $\displaystyle{ x_i\lt y_j }$ then $\displaystyle{ m(XY)\le m(X)+m(Y) }$, that is, the measure is subadditive
• for each $\displaystyle{ x\in\mathbb N }$ and $\displaystyle{ X\in\mathbb N^{*} }$, $\displaystyle{ m(\langle x\rangle X)\le |X|+m(X) }$. Intuitively, if you add an element $\displaystyle{ x }$, it can be in the wrong order compared to at most every other element of $\displaystyle{ X }$, and so the pre-sortedness can be increased by at most the length of $\displaystyle{ X }$.

Those axioms are similar to the axioms of measure theory. However, a measure of presortedness is not a measure as in measure theory, since it is not defined over a set but over sequence.

## 2. Optimal Algorithm

It is well known that an optimal comparison sort requires to compare $\displaystyle{ O(n\log n) }$ pairs of elements in a sequence. That is, the decision tree complexity is $\displaystyle{ O(n\log n) }$. However, when more informations is known about how much a sequence is presorted, more optimal bounds can be devised. This notion is now formalized.

Given a measure of pre-sortedness $\displaystyle{ m }$, a sequence $\displaystyle{ X=\langle x_1,\dots,x_n\rangle }$, $\displaystyle{ z\ge m(X) }$, let $\displaystyle{ \mathtt{below}(z,X, m) }$ be the set of permutations of $\displaystyle{ X }$ whose measure is at most $\displaystyle{ Z }$. Then let $\displaystyle{ \mathtt{below}(X, m)=\mathtt{below}(m(X), X, m) }$ the set of permutations whose measure is at most the measure of $\displaystyle{ X }$.

A sorting algorithm $\displaystyle{ S }$ which takes as input $\displaystyle{ X }$ and $\displaystyle{ z }$ is said to be weakly $\displaystyle{ m }$-optimal if its time complexity is $\displaystyle{ O(\max(n, \log|\mathtt{below}(z, X, m)|)) }$. That is, the number of operations is logarithmic in the number of possible permutations whose measure is at most $\displaystyle{ z }$. This is optimal in the sens that simply selecting an element in a set of size $\displaystyle{ N }$ requires $\displaystyle{ \log(N) }$ bits of information.

Similarly, a sorting algorithm which takes as input $\displaystyle{ X }$ is $\displaystyle{ m }$-optimal if its time complexit is $\displaystyle{ O(\max(n, \log|\mathtt{below}(z, X, m)|)) }$. When $\displaystyle{ m(X) }$ is computable in linear time, a weakly $\displaystyle{ m }$-optimal algorithm is automatically $\displaystyle{ m }$-optimal. However, if $\displaystyle{ m }$ is more complex, it is possible that computing $\displaystyle{ m(X) }$ is actully more costly than sorting the sequence in the first place, and thus only an upper bound $\displaystyle{ z }$ of $\displaystyle{ m(X) }$ can be used.

Similarly, a decision tree is weakly $\displaystyle{ m }$-optimal if its complexity is $\displaystyle{ O(\max(n, \log|\mathtt{below}(z, X, m)|)) }$ and it is $\displaystyle{ m }$-optimal if its complexity $\displaystyle{ O(\max(n, \log|\mathtt{below}(X, m)|)) }$.

### 2.1. Existence of Decision Tree

For each measure $\displaystyle{ m }$, there exists a weakly $\displaystyle{ m }$-optimal decision tree.

If the decision tree complexity of $\displaystyle{ m }$ is $\displaystyle{ O(\max(|X|, \log|\mathtt{below}(X, m)|)) }$, there exists an $\displaystyle{ m }$-optimal decision tree. This decision tree's root compute $\displaystyle{ m(X) }$. Once $\displaystyle{ m(X) }$ is computed in a node, the weakly $\displaystyle{ m }$-optimal decision tree for $\displaystyle{ m(X) }$ is appended at this node.

The existence of the tree does not implie that there exists (weakly) $\displaystyle{ m }$-optimal sorting algorithm, as computing the decision tree may be costly.

## 3. Examples

Here is a list of measures of presortedness $\displaystyle{ m }$ and related (weakly) $\displaystyle{ m }$-optimal algorithms. Let $\displaystyle{ X=\langle x_1,\dots,x_n\rangle }$ be fixed for the remaining of the section.

Let us introduce a sorting algorithm that will be optimal for multiple measure. Let's call local insertion sort the algorithm that consists in iterating on the sequence and adding each element in a finger tree.

### 3.1. The Zero Measure

The constant function 0 is the most trivial measure of presortedness. Any sorting function running in $\displaystyle{ O(n\log n) }$-time, such as heapsort and mergesort is $\displaystyle{ 0 }$-optimal.

### 3.2. The Indicator Function

The indicator function $\displaystyle{ m_{01} }$ of sorted sequence is a measure of sortedness. This function sends sorted sequences to 0 and all other sequences to 1. Any algorithm that check whether a list is sorted, and if it is not sorted apply a $\displaystyle{ 0 }$-optimal sorting algorithm is $\displaystyle{ m_{01} }$-optimal.

### 3.3. Number of Runs

The number of runs, $\displaystyle{ \mathtt{Runs}(X) }$, is the number of increasing sequences in $\displaystyle{ X }$ minus one. It is equivalently defined as the number of $\displaystyle{ i }$ such that $\displaystyle{ x_{i+1}\lt x_i }$. is a measure of presortedness.

Natural merge sort, which consists in using existing runs and merging them, is a $\displaystyle{ \mathtt{Runs} }$-optimal algorithm. The local insertion sort is also Runs-optimal.

### 3.4. Number of Inversions

The number of inversion in $\displaystyle{ X }$, $\displaystyle{ \mathtt{Inv}(X) }$, is the number of pairs $\displaystyle{ i\lt j }$ such that $\displaystyle{ x_i\gt x_j }$. It is a measure of presortedness and the local insertion sort is Inv-optimal.

### 3.5. Number of Deletions

The mininimum number $\displaystyle{ \mathtt{Rem}(X) }$ of elements that need to be removed from $\displaystyle{ X }$ to obtain a sorted sequences. It is a measure of presortedness and the local insertion sort is Rem-optimal.

The radius $\displaystyle{ \mathtt{Rad}(X) }$ of $\displaystyle{ X }$[1] is a measure of presortdness.

The following algorithm is Rad-optimal. It consists in iteratively halving the radius until it reaches 0. Halving the radius can be done by three merges of sub-sequences of length $\displaystyle{ \mathtt{Rad}(X) }$.

### 3.7. Minimum of Two Measures

Given two measures of presortdness $\displaystyle{ m_1 }$ and $\displaystyle{ m_2 }$, the measure $\displaystyle{ X\mapsto\min(m_1(X), m_2(X)) }$ is also a measure of presortdness. Given two $\displaystyle{ m_i }$-optimal sorting algorithms $\displaystyle{ S_i }$, the algorithm consisting in executing $\displaystyle{ S_1 }$ and $\displaystyle{ S_2 }$ in parallel and returning the first output is a $\displaystyle{ \min(m_1,m_2) }$-optimal algorithm.

The content is sourced from: https://handwiki.org/wiki/Measure_of_presortedness

### References

1. Estivill-Castro, Vladimir; Wood, Derick (October 1989). "A new measure of presortdness". Information andComputation 83 (1): 111–119. doi:10.1016/0890-5401(89)90050-3.  https://dx.doi.org/10.1016%2F0890-5401%2889%2990050-3
More
This entry is offline, you can click here to edit this entry!