Parallel Algorithms For Merging And Sorting

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