English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Zendy Plus

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Zendy Tools

Zendy Open

The problem of merging sorted lists in the least number of pairwisecomparisons has been solved completely only for a few special cases. Graham andKarp \cite{taocp} independently discovered that the tape merge algorithm isoptimal in the worst case when the two lists have the same size. In the seminalpapers, Stockmeyer and Yao\cite{yao}, Murphy and Paull\cite{3k3}, andChristen\cite{christen1978optimality} independently showed when the lists to bemerged are of size $m$ and $n$ satisfying $m\leqn\leq\lfloor\frac{3}{2}m\rfloor+1$, the tape merge algorithm is optimal in theworst case. This paper extends this result by showing that the tape mergealgorithm is optimal in the worst case whenever the size of one list is nolarger than 1.52 times the size of the other. The main tool we used to provelower bounds is Knuth's adversary methods \cite{taocp}. In addition, we showthat 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 mightbe interesting in its own right. Moreover, we design a simple procedure toachieve constant improvement of the upper bounds for $2m-2\leq n\leq 3m $.

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