A Simple Algorithm for Merging Two Disjoint Linearly Ordered Sets
- 1 March 1972
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Computing
- Vol. 1 (1) , 31-39
- https://doi.org/10.1137/0201004
Abstract
In this paper we present a new algorithm for merging two linearly ordered sets which requires substantially fewer comparisons than the commonly used tape merge or binary insertion algorithms. Bounds on the difference between the number of comparisons required by this algorithm and the information theory lower bounds are derived. Results from a computer implementation of the new algorithm are given and compared with a similar implementation of the tape merge algorithm.Keywords
This publication has 1 reference indexed in Scilit:
- Optimal merging of 2 elements with n elementsActa Informatica, 1971