Sorting Shuffled Monotone Sequences

AbstractWe 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