Murphy, Paul E. & Paull, Marvin C.. Minimum Comparison Merging of Sets Of Approximately Equal Size. Retrieved from https://doi.org/doi:10.7282/T33200CN
AbstractThe problem of merging ordered sets in the least number of binary comparisons has been solved completely only for a few special cases. When the sets to be merged are of size m and ml (m:5m' ~~m+4) the tape merge algorithm has been shown to be optimum in the worst case. This paper significantly extends these results by showing that the tape merge algorithm is optimum in the worst case whenever one set is no larger than 1.5 times the size of the other. This result is obtained by defining an interesting and amusing two-player game isomorphic to the problem of merging ordered sets and analyzing the optimum strategies for each player. The form of this result should be applicable to the solution of similar sorting and selection problems.
RightsThis Item is protected by copyright and/or related rights.You are free to use this Item in any way that is permitted by the copyright and related rights legislation that applies to your use.For other uses you need to obtain permission from the rights-holder(s).
