Minimal Mergesort
Tadao Takaoka
Department of Computer Science
University of Canterbury
Abstract
We present a new adaptive sorting algorithm, called minimal merge sort, which merges the ascending runs in the input list from shorter to longer, that is, merging the shortest two lists each time. We show that this algorithm is optimal with respect to the new measure of presortedness, called entropy.
Keywords: adaptivesort, minimal mergesort, ascending runs, entropy