Paper Info
Title
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_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.
Year
DOI
Venue
2019
10.1007/s11227-018-2623-z
The Journal of Supercomputing
Keywords
Field
DocType
Integer merging, Parallel algorithm, Shared memory, Concurrent read, Constant-time algorithm
Integer,Subroutine,Shared memory,Computer science,Parallel algorithm,Parallel computing,Sorted array,Sorting,Database design,Merge (version control)
Journal
Volume
Issue
ISSN
75
2
1573-0484
Citations 
PageRank 
References 
0
0.34
17
Authors
1
Name
Order
Citations
PageRank
Hazem M. Bahig1247.61