Parallel Algorithms For Merging And Sorting
Abbreviated Journal Title
COMPUTATION; Computer Science, Information Systems
We present an O(log(min(m,n,j))-time sequential algorithm to select the jth-smallest element of an array resulting from the merging of two sorted arrays A and B of sizes m and n. This algorithm is then used to design two parallel algorithms to partition A and B into p subarrays of size O((m + n)/p) in O(N / p + log N) and O(N / p + log p log N) times on CREW PRAM AND EREW PRAM models with p processors, where N = m + n. A third parallel algorithm has been presented that partitions A and B in O(N / p + log p log N) time into p pairs of subarrays of size O(N / p) on EREW PRAM with p processors without using any selection algorithm. Finally, these partitioning algorithms are used to obtain optimal parallel merging and sorting algorithms on CREW PRAMS and EREW PRAMS.
"Parallel Algorithms For Merging And Sorting" (1991). Faculty Bibliography 1990s. 216.