Merging on PRAM

Abstract

Many data sets to be merged consist of (1) n distinct keys and (2) the keys are serial numbers. Merging such data can be represented as merging two sorted arrays A = (a , a , . . . , a ) and B = (b , b , . . . , b ) of records such that (1) the keys are distinct; (2) 0≤ a · key, b · <n, ∀0 ≤ i < n and 0 ≤ j <n , where n = n + n and key is the primary key of the record. We present an optimal deterministic merging algorithm on EREW PRAM in O(n/p) time, where p is the number of processors and 1 ≤ p < n. The algorithm uses linear number of space. We also extend the algorithm to capture repeated keys such that the repetition of the key is at most constant. o 1 n1-1 0 1 n2-1 i j 1 2 1 2