On the Optimality of Tape Merge (Xiaoming Sun)

Abstract

The problem of merging two sorted lists in the least number of pairwise comparisons has been completely solved only for a few special cases. For example, Gramham, and Hwang and Lin independently showed how to merge 2 elements with n elements optimally, then Hwang and Murphy independently solved the problem for 3 elements, Monting do it for 4 and 5 elements. Graham and Karp 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, Murphy and Paull, and Christen independently showed when the lists to be merged are of size m and n satisfying m ≤ n ≤ 1.5m, the tape merge algorithm is optimal in the worst case. In this talk we 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 38/25 times the size of the other. The main tool we used to prove lower bounds is Knuth’s adversary methods. In addition, we show that the lower bound cannot be improved to 9/5 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 2m-2 ≤ n ≤ 3m.

This is a joint work with Qian Li and Jialin Zhang.

Time

Speaker

Room