On the optimality of tape merge of two lists with similar size

DOI10.1007/S00453-020-00690-XMaRDI QIDQ2182103zbMATH OpenOpenAlexFDO

Authors Qian Li, Xiaoming Sun, Jialin Zhang

Publication date 21 May 2020

Published in Algorithmica (Search for Journal in Brave)

Full work available at URL https://drops.dagstuhl.de/opus/volltexte/2016/6821/

zbMATH Keywords

adversary methodoptimal mergecomparison-based modeltape merge

Mathematics Subject Classification ID

Searching and sorting (68P10) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Recommendations

• On the optimality of tape merge of two lists with similar size
• Optimal expected-time algorithms for merging
• Two Probabilistic Results on Merging
• Optimizing stable in-place merging.
• Reaching the bound in the \((2,n)\) merging problem

Cites work

• scientific article; zbMATH DE number 2079316 (Why is no real title available?)
• A Class of Merging Algorithms
• A Fast Merging Algorithm
• A Simple Algorithm for Merging Two Disjoint Linearly Ordered Sets
• Algorithms for the Generalized Sorting Problem
• An improvement of the binary merge algorithm
• Average-case analysis of the merging algorithm of Hwang and Lin
• Merging of 4 or 5 elements with n elements
• Merging with parallel processors
• Minimean Merging and Sorting: An Algorithm
• Minimum comparison merging of sets of approximately equal size
• On generalized comparison-based sorting problems
• On the Optimality of Linear Merge
• Optimal Merging of 3 Elements with n Elements
• Optimal expected-time algorithms for merging
• Optimal merging of 2 elements with n elements
• Searching monotone multi-dimensional arrays
• Searching ordered structures
• Significant Improvements to the Hwang-Lin Merging Algorithm
• The Information-Theoretic Bound is Good for Merging
• Two Probabilistic Results on Merging

Cited in

(2)

• Optimal expected-time algorithms for merging
• On the optimality of tape merge of two lists with similar size

This page was built for publication: On the optimality of tape merge of two lists with similar size

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2182103)