An improvement of the binary merge algorithm

In this paper, we are concerned with the merging of two linearly-ordered listsA andB consisting of elements:a1merging algorithm was considered very efficient for merging two lists of arbitrary sizes. Recently, Manacher was able to develop methods which reduce the number of pairwise comparisons required in the Hwang-Lin algorithm by a factor 31/336m. We develop in this paper a new method which further improves this factor to 52/336m. It is possible that even larger improvements could be achieved.