<p>Take a look at </p>

<p><a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.45.8017" rel="nofollow">http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.45.8017</a>.</p>

<p>One measure of disorder according to the paper is the Shuffled Monotone Subsequences (SMS, page 7 bottom) which is more than you asked for.</p>

<p>The paper </p>

<p>"Sorting shuffled monotone sequences" by Christos Levcopoulos and Ola Petersson </p>

<p><a href="http://www.springerlink.com/content/79551g82q1p856n1/" rel="nofollow">http://www.springerlink.com/content/79551g82q1p856n1/</a></p>

<p>gives an algorithm with the optimal runtime w.r.t. that measure which is what you seek.</p>

CC BY-SA 3.0
2012-03-12T20:13:04.630Z
2012-03-13T11:49:21.390Z
2012-03-13T11:49:21.390Z
Andreas Björklund
<p>In the following I looked at sorting <em>networks</em> to do the job:</p>

<p><a href="http://www.sciencedirect.com/science/article/pii/S074373150500136X" rel="nofollow">http://www.sciencedirect.com/science/article/pii/S074373150500136X</a> .</p>

<p>Joel Seiferas</p>

CC BY-SA 3.0
2016-08-09T18:39:55.237Z
2016-08-09T18:39:55.237Z
Joel Seiferas
<p>Here's a Levcopoulos-Petersson sorting algorithm reference, but a different one somewhat older than the one in Andreas' answer:</p>

<p>Levcopoulos, Christos; Petersson, Ola (1989), "Heapsort - Adapted for Presorted Files", WADS '89: Proceedings of the Workshop on Algorithms and Data Structures, Lecture Notes in Computer Science, 382, London, UK: Springer-Verlag, pp. 499–509, doi:10.1007/3-540-51542-9_41.</p>

<p>There's a description of the algorithm in <a href="http://en.wikipedia.org/wiki/Cartesian_tree#Application_in_sorting">http://en.wikipedia.org/wiki/Cartesian_tree#Application_in_sorting</a> from which the O(n log k) bound is easy to see. More precisely the time for the algorithm is $O(\sum\log k_i)$ where $k_i$ is the number of intervals containing input item $x_i$. In a $k$-idiotic sequence, each $k_i$ is uniformly bounded by $k$ so the total time is just $O(n\log k)$.</p>

CC BY-SA 3.0
2012-03-13T01:05:40.320Z
Cool. Wikipedia ref wins over closed firewall...
Sariel Har-Peled
CC BY-SA 3.0
2012-03-13T06:08:34.817Z
@SarielHar-Peled: I agree.
Andreas Björklund
CC BY-SA 3.0
2012-03-12T23:35:21.260Z
2012-03-12T23:35:21.260Z
David Eppstein
<p>I hope somebody knows a ref to this, so I do not have to read the literature...</p>

<p>Consider a sequence of numbers $x_1, \ldots, x_n$. Think about the sequence as $n-1$ intervals $[x_1, x_2], [x_2, x_3], \ldots, [x_{n-1},x_n]$. Clearly, the original sequence is bitonic if any point on the real line stabs at most 2 intervals. We will refer to a sequence where a point stabs at most $k$ intervals as being <em>$k$-idiotic</em>. Visually, if you draw the graph of the sequence (i.e., connect the points $p_i =(i,x_i)$ in order), then the above corresponds to the condition that no horizontal line intersects the graph more than $k$ times.</p>

<p>It is not too hard (but not too easy, either) to see that $k$-idiotic sequences can be sorted in $O( n \log k )$ time, which is clearly optimal.</p>

<p>Question: This result should be known. Do you know any appropriate ref?</p>

<ds.algorithms><reference-request><sorting>
Sorting "k-tonic" sequences
Sariel Har-Peled
# Sorting "k-tonic" sequences

(Asked by: username_0 on 2012-03-12)

I hope somebody knows a ref to this, so I do not have to read the literature...

Consider a sequence of numbers $x\_1, \ldots, x\_n$. Think about the sequence as $n-1$ intervals $[x\_1, x\_2], [x\_2, x\_3], \ldots, [x\_{n-1},x\_n]$. Clearly, the original sequence is bitonic if any point on the real line stabs at most 2 intervals. We will refer to a sequence where a point stabs at most $k$ intervals as being *$k$-idiotic*. Visually, if you draw the graph of the sequence (i.e., connect the points $p\_i =(i,x\_i)$ in order), then the above corresponds to the condition that no horizontal line intersects the graph more than $k$ times.

It is not too hard (but not too easy, either) to see that $k$-idiotic sequences can be sorted in $O( n \log k )$ time, which is clearly optimal.

Question: This result should be known. Do you know any appropriate ref?

**Tags:** ds.algorithms, reference-request, sorting

---

## 3 answers

### Answer by username_3 on 2012-03-12. Score: 10 | Accepted answer

Here's a Levcopoulos-Petersson sorting algorithm reference, but a different one somewhat older than the one in Andreas' answer:

Levcopoulos, Christos; Petersson, Ola (1989), "Heapsort - Adapted for Presorted Files", WADS '89: Proceedings of the Workshop on Algorithms and Data Structures, Lecture Notes in Computer Science, 382, London, UK: Springer-Verlag, pp. 499–509, doi:10.1007/3-540-51542-9\_41.

There's a description of the algorithm in <http://en.wikipedia.org/wiki/Cartesian_tree#Application_in_sorting> from which the O(n log k) bound is easy to see. More precisely the time for the algorithm is $O(\sum\log k\_i)$ where $k\_i$ is the number of intervals containing input item $x\_i$. In a $k$-idiotic sequence, each $k\_i$ is uniformly bounded by $k$ so the total time is just $O(n\log k)$.

> **Comments:**
> **username_0**: Cool. Wikipedia ref wins over closed firewall...  
> **username_1**: @SarielHar-Peled: I agree.  

---

### Answer by username_1 on 2012-03-12. Score: 6

Take a look at

<http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.45.8017>.

One measure of disorder according to the paper is the Shuffled Monotone Subsequences (SMS, page 7 bottom) which is more than you asked for.

The paper

"Sorting shuffled monotone sequences" by Christos Levcopoulos and Ola Petersson

<http://www.springerlink.com/content/79551g82q1p856n1/>

gives an algorithm with the optimal runtime w.r.t. that measure which is what you seek.


---

### Answer by username_2 on 2016-08-09. Score: 1

In the following I looked at sorting *networks* to do the job:

<http://www.sciencedirect.com/science/article/pii/S074373150500136X> .

Joel Seiferas


---

