Sorting Shuffled Monotone Sequences

We present a new sorting algorithm that adapts to existing order within an input sequence. Let k be the smallest integer such that a sequence X of length n can be reduced to the empty sequence by the removal of k monotone, increasing or decreasing subsequences. The algorithm, Slabsort, sorts X in O(n log k) time, without knowing k beforehand, which is optimal in a comparison-based model.

Authors

• C. Levcopoulos
• O. Petersson

Keywords

No keywords are indexed for this paper.