Abstract
We present a new optimal deterministic parallel algorithm for merging two sorted arrays A = (a(0),a(1),(...),a(n1-1)) and B = (b(0),b(1),(...),b(n2-1)) of integers. The elements of two sorted arrays are drawn from a domain of integers [0, n - 1], where n = Max(n(1), n(2))The algorithm takes O (log n) time and O (n) space using n/log n processors on EREW PRAM. Also, the algorithm is stable.