SUBLINEAR MERGING AND NATURAL MERGESORT

The complexity of merging two sorted sequences into one is linear in t he worst case as well as in the average case. There are, however, inst ances for which a sublinear number of comparisons is sufficient. We co nsider the problem of measuring and exploiting such instance easiness. The merging algorithm presented, Adaptmerge, is shown to adapt optima lly to different kinds of measures of instance easiness. In the sortin g problem the concept of instance easiness has received a lot of atten tion, and it is interpreted by a measure of presortedness. We apply Ad aptmerge in the already adaptive sorting algorithm Natural Mergesort. The resulting algorithm, Adaptive Mergesort, optimally adapts to sever al, known and new, measures of presortedness. We also prove some inter esting results concerning the relation between measures of presortedne ss proposed in the literature.