期刊名称：International Journal of Advanced Computer Science and Applications(IJACSA)
印刷版ISSN：2158-107X
电子版ISSN：2156-5570
出版年度：2021
卷号：12
期号：1
页码：685-691
DOI：10.14569/IJACSA.2021.0120179
出版社：Science and Information Society (SAI)
摘要：The k integer-merging problem is to merge the k sorted arrays into a new sorted array that contains all elements of Ai,∀ i. We propose a new parallel algorithm based on exclusive read exclusive write shared memory. The algorithm runs in O(log n) time using n/log n processors. The algorithm performs linear work, O(n), and has optimal cost. Furthermore, the total work done by the algorithm is less than the best-known previous parallel algorithms for k merging problem.
关键词：Merging; parallel algorithm; shared memory; optimality; linear work
