A new constant-time parallel algorithm for merging

Abstract

Merging is the process of constructing a sorted array C from two sorted arrays A and B of lengths n and n , 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. A B