Parallel merging with restriction

Abstract

In this paper, we study the merging of two sorted arrays A=(a1,a2,..., an1) and B=(b1,b2,...,bn2) on EREW PRAM with two restrictions: (1) The elements of two arrays are taken from the integer range [1,n], where n=Max(n ,n ). (2) The elements are taken from either uniform distribution or non-uniform distribution such that #\{a∈A,b ∈ B {s.t.} ,a,b ∈ [(i-1) {n}{p}+1,i {n}p] }=O( n}{p} , for 1 i p∈(number of processors). We give a new optimal deterministic algorithm runs in O( {n}{p}) time using p processors on EREW PRAM. For p= n (g)} {n}}; the running time of the algorithm is O(log∈ n) which is faster than the previous results, where log∈ n=log∈log∈ n for g>1 and log∈ n=log∈n. We also extend the domain of input data to [1,n ], where k is a constant. © 2007 Springer Science+Business Media, LLC. 1 2 (g) (g) (g-1) (1) k