Minimum Comparison Merging of Sets Of Approximately Equal Size

The 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.Technical report DCS-TR-7