Institute of Mathematics and Computer Science, Wroc?aw University of Technology, ul. Wybrze?e Wyspiańskiego 27, 50-370 Wroc?aw, Poland

摘要

We introduce a new stable in place merging algorithm that needs O(m log (n/m + 1))) comparisons and O(m+n) assignments. According to the lower bounds for merging our algorithm is asymptotically optimal regarding the number of comparisons as well as assignments. The stable algorithm is developed in a modular style out of an unstable kernel for which we give a definition in pseudocode.