In this paper, we are concerned with the merging of two linearly-ordered listsA andB consisting of elements:a1<a2<...<b n . The Hwang-Lin merging algorithm was considered very efficient for merging two lists ...
详细信息
In this paper, we are concerned with the merging of two linearly-ordered listsA andB consisting of elements:a1algorithm 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.
暂无评论