ON PARALLEL INTEGER MERGING

The problem of merging two sorted arrays A = (a1, a2, …, an) and B = (b1, b2, …, bn) is considered. For input elements that are drawn from a domain of integers [1…s] we present an algorithm that runs in O(log log log s) time using n/log log log s CREW PRAM processors (optimal speed-up) and O(nsε{lunate}) space, where n = n1 + n2. For input elements that are drawn from a domain of integers [1…n] we present a second algorithm that runs in O(α(n)) time (where α(n) is the inverse of Ackermann’s function) using n/α(n) CREW PRAM processors and linear space. This second algorithm is non-uniform; however, it can be made uniform at a price of a certain loss of speed, or by using a CRCW PRAM. © 1993 Academic Press, Inc.