12
$\begingroup$

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?

Improve this question
$\endgroup$

3 Answers 3

Reset to default
10
$\begingroup$

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)$.

Improve this answer
$\endgroup$
2
  • 2
    $\begingroup$ Cool. Wikipedia ref wins over closed firewall... $\endgroup$
    – Sariel Har-Peled
    Commented Mar 13, 2012 at 1:05
  • 1
    $\begingroup$ @SarielHar-Peled: I agree. $\endgroup$
    – Andreas Björklund
    Commented Mar 13, 2012 at 6:08
6
$\begingroup$

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.

Improve this answer
$\endgroup$
1
$\begingroup$

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

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

Joel Seiferas

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.