Measure of presortedness

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.

Definition

Let ${\mathbb{\mathbb{N}}}^{*}$ represents finite sequence of natural numbers. Let $m:{\mathbb{\mathbb{N}}}^{*}\to \mathbb{\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 $X=⟨x_1,\dots ,x_n⟩$ is in ascending order, then $m(X)=0$, that is, the measure of presortedness of sorted sequences is 0.
• let $X=⟨x_1,\dots ,x_n⟩$ and $Y=⟨y_1,\dots ,y_n⟩$. If $x_i<x_j$ iff $y_i<y_j$, then $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 $Y$ is a subsequence of $X$ then $m(Y)\le m(X)$, that is, $m$ is monotonic for the subsequence relation
• let $X=⟨x_1,\dots ,x_n⟩$ and $Y=⟨y_1,\dots ,y_n⟩$. If for each $i,j$, $x_i<y_j$ then $m(XY)\le m(X)+m(Y)$, that is, the measure is subadditive
• for each $x\in \mathbb{\mathbb{N}}$ and $X\in {\mathbb{\mathbb{N}}}^{*}$, $m(⟨x⟩X)\le |X|+m(X)$. Intuitively, if you add an element $x$, it can be in the wrong order compared to at most every other element of $X$, and so the pre-sortedness can be increased by at most the length of $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.

Optimal algorithm

It is well known that an optimal comparison sort requires to compare $O(n\log n)$ pairs of elements in a sequence. That is, the decision tree complexity is $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 $m$, a sequence $X=⟨x_1,\dots ,x_n⟩$, $z\ge m(X)$, let $\mathtt{b}\mathtt{e}\mathtt{l}\mathtt{o}\mathtt{w}(z,X,m)$ be the set of permutations of $X$ whose measure is at most $Z$. Then let $\mathtt{b}\mathtt{e}\mathtt{l}\mathtt{o}\mathtt{w}(X,m)=\mathtt{b}\mathtt{e}\mathtt{l}\mathtt{o}\mathtt{w}(m(X),X,m)$ the set of permutations whose measure is at most the measure of $X$.

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

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

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

Existence of decision tree

For each measure $m$, there exists a weakly $m$-optimal decision tree.

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

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

Examples

Here is a list of measures of presortedness $m$ and related (weakly) $m$-optimal algorithms. Let $X=⟨x_1,\dots ,x_n⟩$ 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.

The zero measure

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

The indicator function

The indicator function $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 $0$-optimal sorting algorithm is $m_{01}$-optimal.

Number of runs

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

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

Number of inversions

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

Number of deletions

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

Radius

The radius $\mathtt{R}\mathtt{a}\mathtt{d}(X)$ of $X$ 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 $\mathtt{R}\mathtt{a}\mathtt{d}(X)$.

Minimum of two measures

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

References

• Mannila, H (1985). "Measures of Presortedness and Optimal Sorting Algorithms". IEEE Trans. Comput (C-34): 318–325.