On Parallel Integer Merging

The problem of merging two sorted arrays A = (a 1, a 2, .. ., a n 1 ) and B = (b 1, b 2, .. ., b n 2 ) 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 = n 1 + n 2. 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.

Authors

• O. Berkman
• U. Vishkin

Keywords

No keywords are indexed for this paper.