Abstract
Given two sorted arrays
and
, where their elements are drawn from a linear range in
n
and
n
= Max(
n
1
,
n
2
). The merging of two sorted arrays is one of the fundamental problems in computer science. The main contribution of this work is to give a new merging algorithm on a EREW PRAM. The algorithm is cost optimal, deterministic and simple. The algorithm uses
processors and
O
(
n
) storage. We also give the conditions that make the algorithm run in a constant time on a EREW PRAM.