Abstract
Merging is the process of constructing a sorted array
C
from two sorted arrays
A
and
B
of lengths
n
A
and
n
B
,
respectively, such that array
C
contains the elements of arrays
A
and
B
. The problem is a fundamental subroutine in many applications such as tree reconstruction, database design, and sorting. In this paper, we present a constant-time integer merging algorithm on a shared memory model with a concurrent read operation. No constant-time algorithm for integer merging on this model was designed previously. The algorithm, which is based on cross-rank and address strategy, works when the elements of the inputs belong to the integer domain. The presented algorithm has the following advantages:- (1) running in constant time; (2) stable; (3) simple; (4) optimal when the domain of integers is less than or equal to the size of the inputs and the number of processors is equal to size of the inputs; and (5) deterministic.