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?

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

$\endgroup$
  • 2
    $\begingroup$ Cool. Wikipedia ref wins over closed firewall... $\endgroup$ – Sariel Har-Peled Mar 13 '12 at 1:05
  • 1
    $\begingroup$ @SarielHar-Peled: I agree. $\endgroup$ – Andreas Björklund Mar 13 '12 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.

$\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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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