K-sorted sequence

A sequence ${\displaystyle [a_{1},\dots ,a_{n}]}$ is ${\displaystyle k}$-sorted if and only if each range of length ${\displaystyle 2k+2}$, ${\displaystyle [a_{i},a_{i+1},\dots ,a_{i+2k+2}]}$ is ${\displaystyle k}$-sorted.

Given a sequence a ${\displaystyle k}$-sorted sequence ${\displaystyle [a_{1},\dots ,a_{n}]}$ and its sorted permutation ${\displaystyle [a_{\sigma _{1}},\dots ,a_{\sigma _{n}}]}$, ${\displaystyle |i-\sigma _{i}|}$ is at most ${\displaystyle k}$.

Deciding whether a sequence ${\displaystyle [a_{1},\dots ,a_{n}]}$ is ${\displaystyle k}$-sorted can be done in linear time and constant space by a streaming algorithm. It suffices, for each ${\displaystyle 1\leq i<n-k}$, to keep track of ${\displaystyle \max(a_{j}\mid j\leq i)}$ and to check that ${\displaystyle a_{i+k}\geq \max(a_{j}\mid j\leq i)}$.

Computing the radius of a sequence can be computed in linear time and space. This follows from the fact that it can be defined as ${\displaystyle \max(i-j\mid \min(a_{k}\mid k\geq i)<\max(a_{k}\mid k\leq j))}$.

Given a ${\displaystyle 2k}$-sorted sequence ${\displaystyle \alpha =[a_{1},\dots ,a_{n}]}$, it is possible to compute a ${\displaystyle (k-1)}$-sorted permutation ${\displaystyle \alpha '}$ of ${\displaystyle \alpha }$ in linear time and constant space.

First, given a sequence ${\displaystyle \beta =[b_{1},\dots ,b_{2k}]}$, lets say that this sequence is partitioned if the ${\displaystyle k}$-smaller elements are in ${\displaystyle [b_{1},\dots ,b_{k}]}$ and the ${\displaystyle k}$-greater elements are in ${\displaystyle [b_{k+1},\dots ,b_{2k}]}$. Lets call partitioning the action of reordering the sequence ${\displaystyle \beta }$ into a partitioned permutation. This can be done in linear time by first finding the median of ${\displaystyle b}$ and then moving elements to the first or second half depending on whether they are smaller or greater than the median.

The sequence ${\displaystyle \alpha '}$ can be obtained by partitioning the blocks of elements at position ${\displaystyle [2k(i-1)+1,\dots ,2ki]}$, then by partitioning the blocks of elements at position ${\displaystyle [2k(i-1)+k+1,\dots ,2ki+k]}$, and then again the elements at position ${\displaystyle [2k(i-1)+1,\dots ,2ki]}$ for each number ${\displaystyle i}$ such that those sequences are defined.

Using ${\displaystyle {\frac {n}{2k}}}$ processors, with no shared read nor write access to memory, the same algorithm can be applied in ${\displaystyle O(k)}$ time, since each partition of a sequence can occur in parallel.

Merging two ${\displaystyle k}$-sorted sequences ${\displaystyle \alpha ^{1}=[a_{1}^{1},\dots ,a_{n}^{1}]}$ and ${\displaystyle \alpha =[a_{1}^{2},\dots ,a_{m}^{2}]}$ can be done in linear time and constant space.

First, using the preceding algorithm, both sequences should be transformed into ${\displaystyle k/2}$-sorted sequences.

Let's construct iteratively an output sequence ${\displaystyle \omega }$ by removing content from both ${\displaystyle \alpha ^{i}}$ and adding it in ${\displaystyle \omega }$.

If both ${\displaystyle \alpha ^{i}}$'s are empty, then it suffices to return ${\displaystyle \omega }$. Otherwise, let us assume that ${\displaystyle \alpha ^{1}}$ is empty and not ${\displaystyle \alpha ^{2}}$, it suffices to remove the content of ${\displaystyle \alpha ^{2}}$ and append it to ${\displaystyle \omega }$. The case where ${\displaystyle \alpha ^{2}}$ is empty and not ${\displaystyle \alpha ^{1}}$ is similar by symmetry.

Let us consider the case where neither ${\displaystyle \alpha ^{i}}$ is empty. Let us call ${\displaystyle A^{1}=\max(a_{i}^{1}\mid 1\leq i\leq k/2)}$ and ${\displaystyle A^{2}=\max(a_{i}^{2}\mid 1\leq i\leq k/2)}$, they are the greatest of the ${\displaystyle k/2}$-firsts elements of each list. Let us assume that ${\displaystyle A^{1}<A^{2}}$, the other case is similar by symmetry. Remove ${\displaystyle a_{1}^{1},\dots ,a_{k/2}^{1}}$ from ${\displaystyle \alpha ^{1}}$ and remove ${\displaystyle \{a_{j}^{2}\mid 1\leq j\leq k/2,a_{j}^{2}\leq A^{1}\}}$ from ${\displaystyle \alpha ^{2}}$ and add them to ${\displaystyle \omega }$.

A ${\displaystyle k}$-sorted sequence can be sorted by applying the halving algorithm given above ${\displaystyle \log _{2}(k)}$ times. This takes ${\displaystyle O(n\log k)}$ time on a sequential machine, or ${\displaystyle O(k\log k)}$ time using ${\displaystyle O(n)}$ processors.

Since each sequence ${\displaystyle \alpha =[a_{1},\dots ,a_{n}]}$ is necessarily ${\displaystyle n}$-sorted, it suffices to apply the halving algorithm ${\displaystyle \log _{2}\left({\frac {n}{k}}\right)}$-times. Thus, ${\displaystyle k}$-sorting can be done in ${\displaystyle O(n\log(n/k))}$-time. This algorithm is Par-optimal, that is, there exists no sequential algorithm with a better worst-case complexity.