Splitsort - An Adaptive Sorting Algorithm

Abstract We present a new sorting algorithm, called Splitsort which adapts to existing order within the input sequence. The algorithm is optimal with respect to several known measures of presortedness, including the number of inversions, for which no such simple and space efficient algorithm was known before. The amount of extra space needed is only n + O (log n ) pointers. Splitsort uses a simple data structure and is easy to code. In the worst case Splitsort performs 2. 5 n log 2 n comparisons, but if the input is presorted according to some of the measures it completes the sorting task considerably faster. We also show how a variant of the algorithm can be implemented to run in-place.

Authors

• Christos Levcopoulos
• Ola Petersson

Keywords

No keywords are indexed for this paper.