On Parallel Integer Merging

AbstractThe problem of merging two sorted arrays A = (a1, a2, ..., an1) and B = (b1, b2, ..., bn2) 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ϵ) 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