Optimal Stable Merging

Antonios Symvonis

Basser Department of Computer Science

University of Sydney

Sydney, N.S.W. 2006

Australia

[email protected]

May 17, 1993

Abstract

In this paper we show how to stably merge two sequences A and B of sizes m and n, m <= n, respectively, with O(m + n) assignments, O(m log( nm + 1)) comparisons and using only a constant amount of additional space. This result matches all known lower bound and closes an open problem posed by Dudzinski and Dydek [2] in 1981. Our algorithm is based on the unstable algorithm of Mannila and Ukkonen. All techniques we use have appeared in the literature in more complicated forms but were never combined together. They are powerful enough to make stable all the existing linear in-place unstable algorithms we are aware of. We also present a stable algorithm that requires a linear number of comparisons and assignments which we consider to be the simplest algorithm for in-place merging.

1 Introduction

In this paper, we consider the problem of merging. We are given two sequences A and B of m and n elements, respectively, such that A and B are sorted in increasing order according to a key value of their elements. Without loss of generality, in the rest of the paper we assume that m <= n. The result of merging A and B will be a sequence C of N = m + n elements, consisting of the elements of A and B, such that C is sorted in increasing order according to the same key value of its elements. An element of sequence A is called an A-element. Similarly, we define B-elements.

We assume that initially A and B occupy segments L[0 ? ? ? m ? 1] and L[m ? ? ? N ? 1] of an array L, respectively, and that after the merging C occupies the entire array L[0 ? ? ? N ? 1]. To facilitate the presentation, in the rest of the paper we assume that all arrays are laid down from left to right.

In addition, we may want our merging algorithm to be stable. We say that the merging is stable if the internal ordering of sequences A and B is maintained in the resulting sequence C, i.e., elements with the same key value appear in sequence C in the same order in which they appear in sequences A and B before the merging. (In the case that elements with the same key appear in both sequences, the elements in sequence A are considered to be smaller" than the elements with the same key in sequence B.)

The performance of any merging algorithm is judged according to the number of computation steps it needs to perform the merging as well as the amount of extra space used (in addition to the space for