An efficient parallel algorithm for merging in the postal model

Given two sorted lists A = (a(0), a(1,)...; a(l-1)) and B = (b(0), b(1),; . .., b(m-1)), we are to merge these two lists into a sorted list C = (c(0), c(1),...; c(n-1)), where n=l+m Since this is a fundamental problem useful t o solve many problems such as sorting and graph problems, there have been m any efficient parallel algorithms for this problem. But these algorithms ca nnot be performed efficiently in the postal model since the communication l atency lambda, which is of prime importance in this model, is not needed to be considered for those algorithms. Hence, in this paper we propose an eff icient merge algorithm in this model that runs in 2 lambda 1og n/log(lambda +1) +lambda-1 time by using a new property of the bitonic sequence which is crucial to our algorithm. We also show that our algorithm is near-optimal by proving that the lower bound of this problem in the postal model is f(la mbda)(n/2), where lambda log n - log 2/log ([lambda] + 1) less than or equal to f(lambda) (n/ 2) less than or equal to 2 lambda + 2 lambda log n - log 2/log ([lambda] 1).