The problem of merging sorted lists in the least number of pairwise comparisons has been solved completely only for a few special cases. Graham and Karp taocp independently discovered that the tape merge algorithm is optimal in the worst case when the two lists have the same size. In the seminal papers, Stockmeyer and Yao yao , Murphy and Paull 3k3 , and Christen christen1978optimality independently showed when the lists to be merged are of size @math and @math satisfying @math , the tape merge algorithm is optimal in the worst case. This paper extends this result by showing that the tape merge algorithm is optimal in the worst case whenever the size of one list is no larger than 1.52 times the size of the other. The main tool we used to prove lower bounds is Knuth's adversary methods taocp . In addition, we show that the lower bound cannot be improved to 1.8 via Knuth's adversary methods. We also develop a new inequality about Knuth's adversary methods, which might be interesting in its own right. Moreover, we design a simple procedure to achieve constant improvement of the upper bounds for @math .
A simple partitioning algorithm for merging two disjoint linearly ordered sets is given, and an upper bound on the average number of comparisons required is established. The upper bound is @math , where n is the number of elements in the larger of the two sets, m the number of the smaller, and @math . An immediate corollary is that any sorting problem can be done with an average number of comparisons within @math of the information theoretic bound using repeated merges; it does not matter what the merging order used is. Although the provable bound is @math over the lower bound, computations indicate that the algorithm will asymptotically make only @math more comparisons than the lower bound. The algorithm is compared with the Hwang-Lin algorithm, and modifications to improve average efficiency of this well known algorithm are given.  We derive an asymptotic equivalent to the average running time of the merging algorithm of Hwang and Lin applied on two linearly ordered lists of numbers a 1 <a 2 <. . . <a m and b 1 <b 2 < . . . <b n when m and n tend to infinity in such a way that the ratio ( ) = m n is constant. We show that the distribution of the running time is concentrated around its expectation except when ( ) is a power of 2. When ( ) is a power of 2, we obtain an asymptotic equivalent for the expectation of the running time.