2016/10/11 by Qian Li, Xiaoming Sun, Li, Qian +3
Biochemistry, Genetics and Molecular Biology · Computer Science · Mathematics · #Advanced Combinatorial Mathematics #Algorithms and Data Compression #Computational Complexity (cs.CC) #Data Structures and Algorithms (cs.DS) #F.2.2 #FOS: Computer and information sciences #Genome Rearrangement Algorithms
paper · pdf · doi:10.48550/arxiv.1610.03266
openalex publication_date 2016/10/11 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 \citetaocp 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\citeyao, Murphy and Paull\cite3k3, and Christen\citechristen1978optimality independently showed when the lists to be merged are of size m and n satisfying m≤ n≤\lfloor(3)/(2)m\rfloor+1, 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 \citetaocp. 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 2m-2≤ n≤ 3m .