Optimal parallel merging by counting
Bahig, Hazem;
Abstract
We present a new optimal deterministic parallel algorithm for merging two sorted arrays A = (a0, a1, . . . , an1-1) and B = (b 0, b1, . . . , bn2-1) of integers. The elements of two sorted arrays are drawn from a domain of integers [0, n - 1], where n = Max(n1, n2). The algorithm takes O(log n) time and O(n) space using n/ log n processors on EREW PRAM. Also, the algorithm is stable.
Other data
Title | Optimal parallel merging by counting | Authors | Bahig, Hazem | Keywords | merging; parallel algorithm; PRAM, optimal algorithm | Issue Date | 28-Aug-2007 | Publisher | IEEE | Conference | Proceedings - International Conference on Information Technology-New Generations, ITNG 2007 | ISBN | 0769527760 | DOI | https://api.elsevier.com/content/abstract/scopus_id/34548127043 664 10.1109/ITNG.2007.144 |
Scopus ID | 2-s2.0-34548127043 |
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.