A new constant-time parallel algorithm for merging
Bahig, Hazem;
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
Other data
Title | A new constant-time parallel algorithm for merging | Authors | Bahig, Hazem | Keywords | Concurrent read;Constant-time algorithm;Integer merging;Parallel algorithm;Shared memory | Issue Date | 6-Feb-2019 | Publisher | SPRINGER | Journal | Journal of Supercomputing | Volume | 75 | Start page | 968 | End page | 983 | ISSN | 09208542 | DOI | 10.1007/s11227-018-2623-z | Scopus ID | 2-s2.0-85054334585 | Web of science ID | WOS:000460063500024 |
Recommend this item
Similar Items from Core Recommender Database
Items in Ain Shams Scholar are protected by copyright, with all rights reserved, unless otherwise indicated.