Abstract

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, 1999] independently discovered that the tape merge algorithm is optimal in the worst case when the two lists have the same size. Stockmeyer and Yao [SICOMP, 1980], Murphy and Paull [Inform. Control, 1979], and Christen [1978] independently showed when the lists to be merged are of size m and n satisfying m leq n leq floor(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 used to prove lower bounds is Knuth’s adversary methods [TAOCP, 1999]. 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 leq n leq 3m.

@InProceedings{li_et_al:LIPIcs:2016:6821,
  author =	{Qian Li and Xiaoming Sun and Jialin Zhang},
  title =	{{On the Optimality of Tape Merge of Two Lists with Similar Size}},
  booktitle =	{27th International Symposium on Algorithms and Computation (ISAAC 2016)},
  pages =	{51:1--51:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-026-2},
  ISSN =	{1868-8969},
  year =	{2016},
  volume =	{64},
  editor =	{Seok-Hee Hong},
  publisher =	{Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{http://drops.dagstuhl.de/opus/volltexte/2016/6821},
  URN =		{urn:nbn:de:0030-drops-68219},
  doi =		{10.4230/LIPIcs.ISAAC.2016.51},
  annote =	{Keywords: comparison-based sorting, tape merge, optimal sort, adversary method}
}