Merging on Parallel Models of Computation
Borodin, Allan B.; Hopcroft, John E.
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.
computer science; technical report
Previously Published As