On the Optimality of Tape Merge of Two Lists with Similar Size

doi:10.1007/s00453-020-00690-x

	On the Optimality of Tape Merge of Two Lists with Similar Size
	Li, Qian 1,4; Sun, Xiaoming 2,3; Zhang, Jialin 2,3
	2020-02-19
发表期刊	ALGORITHMICA
ISSN	0178-4617
页码	26
摘要	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 (Sorting Search 3:197-207, 1999) independently discovered that the tape merge algorithm is optimal in the worst case when the two lists have the same size. In their seminal papers, Stockmeyer and Yao (SIAM J Comput 9(1):85-90, 1980), Murphy and Paull (Inf Control 42(1):87-96, 1979), and Christen (On the optimality of the straight merging algorithm, 1978) independently showed when the lists to be merged are of size m and n satisfying m = n =. 3 2 m. + 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 use to prove the lower bound is Knuth's (1999) adversary methods. In addition, we show that the lower bound cannot be improved to 1.8 via Knuth's adversary methods. Moreover, we design a simple procedure, and by invoking this procedure recursively until the remaining subproblem can be solved efficiently by another known algorithm, we achieve constant improvement of the upper bound for 2m - 2 = n = 3m.
关键词	Comparison-based model Tape merge Optimal merge Adversary method
DOI	10.1007/s00453-020-00690-x
收录类别	SCI
语种	英语
资助项目	973 Program of China[2016YFB1000201] ; National Natural Science Foundation of China[61832003] ; National Natural Science Foundation of China[61761136014] ; National Natural Science Foundation of China[61872334] ; National Natural Science Foundation of China[61433014] ; K.C.Wong Education Foundation
WOS研究方向	Computer Science ; Mathematics
WOS类目	Computer Science, Software Engineering ; Mathematics, Applied
WOS记录号	WOS:000516475300001
出版者	SPRINGER
引用统计	被引频次：1[WOS] [WOS记录] [WOS相关记录]
文献类型	期刊论文
条目标识符	http://119.78.100.204/handle/2XEOYT63/14638
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	Zhang, Jialin
作者单位	1.Shenzhen Univ, Shenzhen Inst Comp Sci, Shenzhen, Peoples R China 2.Chinese Acad Sci, Inst Comp Technol, CAS Key Lab Network Data Sci & Technol, Beijing 100190, Peoples R China 3.Univ Chinese Acad Sci, Beijing 100049, Peoples R China 4.Shenzhen Univ, Guangdong Prov Key Lab Popular High Performance C, Shenzhen, Peoples R China
推荐引用方式 GB/T 7714	Li, Qian,Sun, Xiaoming,Zhang, Jialin. On the Optimality of Tape Merge of Two Lists with Similar Size[J]. ALGORITHMICA,2020:26.
APA	Li, Qian,Sun, Xiaoming,&Zhang, Jialin.(2020).On the Optimality of Tape Merge of Two Lists with Similar Size.ALGORITHMICA,26.
MLA	Li, Qian,et al."On the Optimality of Tape Merge of Two Lists with Similar Size".ALGORITHMICA (2020):26.