Merging on Parallel Models of Computation

Abstract

A variety of models have been proposed for the study of synchronous parallel computation. We review these models and study further some prototype problems. Within a spectrum of shared memory models, we show that $\log \log n$ is asymtotically optimal for $n$ processors to merge two sorted lists containing $n$ elements.