Hazem M. Bahig and Hatem M. Bahig
Integer merging, merging records, parallel algorithms, optimal algo- rithm, EREW PRAM
Many data sets to be merged consist of (1) n distinct keys and (2) the keys are serial numbers. Merging such data can be rep- resented as merging two sorted arrays A = (a0, a1, . . . , an1−1) and B = (b0, b1, . . . , bn2−1) of records such that (1) the keys are dis- tinct; (2) 0 ≤ ai · key, bj · key < n, ∀0 ≤ i < n1 and 0 ≤ j < n2, where n = n1 + n2 and key is the primary key of the record. We present an optimal deterministic merging algorithm on EREW PRAM in O n p t ime, 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.
Important Links:
Go Back
