Abstract
The k integer-merging problem is to merge the k sorted arrays into a new sorted array that contains all elements of A(i), for all 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.