Sorting "k-tonic" sequences
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)$.