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

doi:10.1007/s00453-020-00690-x

CORC > 计算技术研究所 > 中国科学院计算技术研究所 > 中国科学院计算技术研究所期刊论文 > 英文

	On the Optimality of Tape Merge of Two Lists with Similar Size
	Li, Qian 1,4; Sun, Xiaoming 2,3; Zhang, Jialin 2,3
刊名	ALGORITHMICA
	2020-02-19
页码	26
关键词	Comparison-based model Tape merge Optimal merge Adversary method
ISSN号	0178-4617
DOI	10.1007/s00453-020-00690-x
英文摘要	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.
资助项目	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
语种	英语
出版者	SPRINGER
WOS记录号	WOS:000516475300001
内容类型	期刊论文
源URL	[http://119.78.100.204/handle/2XEOYT63/14637]
专题	中国科学院计算技术研究所期刊论文_英文
通讯作者	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.