Abstract
The complexity of merging two sorted sequences into one is linear in the worst case as well as in the average case. There are, however, instances for which a sublinear number of comparisons is sufficient. We consider the problem of measuring and exploiting such instance easiness. The merging algorithm presented, Adaptmerge, is shown to adapt optimally to different kinds of measures of instance easiness. In the sorting problem the concept of instance easiness has received a lot of attention, and it is interpreted by a measure of presortedness. We apply Adaptmerge in the already adaptive sorting algorithm Natural Mergesort. The resulting algorithm, Adaptive Mergesort, optimally adapts to several, known and new, measures of presortedness. We also prove some interesting results concerning the relation between measures of presortedness proposed in the literature.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
K. Mehlhorn.Data Structures and Algorithms, Vol. 1. Springer-Verlag, Berlin, 1984.
W. H. Burge. Sorting, trees, and measures of order.Information and Control, 1(3):181–197, 1958.
C. R. Cook and D. J. Kim. Best sorting algorithms for nearly sorted lists.Communications of the ACM, 23 (11):620–624, 1980.
D. E. Knuth.The Art of Computer Programming, Vol. 3. Addison-Wesley, Reading, Mass., 1973.
H. Mannila. Measures of presortedness and optimal sorting algorithms.IEEE Transactions on Computers, 34(4):318–325, 1985.
O. Petersson and A. Moffat. A framework for adaptive sorting. InProceedings of the Third Scandinavian Workshop on Algorithm Theory, pp. 422–433. Lecture Notes in Computer Science, Vol. 621, Springer-Verlag, Berlin, 1992.
M. L. Fredman. How good is the information theory bound in sorting?Theoretical Computer Science, 1:355–361, 1976.
O. Petersson. Adaptive Sorting. Ph.D. thesis, Department of Computer Science, Lund University, Lund, 1990.
H. Mannila and E. Ukkonen. A simple linear-time algorithm for in situ merging.Information Processing Letters, 18(4):203–208, 1984.
A. Moffat. Adaptive merging and a naturally Natural Merge Sort. InProceedings of the 14th Australian Computer Science Conference, pp. 08.1–08.8, 1991.
Author information
Authors and Affiliations
Additional information
Communicated by Takao Nishizeki.
Rights and permissions
About this article
Cite this article
Carlsson, S., Levcopoulos, C. & Petersson, O. Sublinear merging and natural mergesort. Algorithmica 9, 629–648 (1993). https://doi.org/10.1007/BF01190160
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01190160