Merging on Parallel Models of Computation
Collections
Author
Borodin, Allan B.
Hopcroft, John E.
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.
Date Issued
1981-09
Publisher
Cornell University
Keywords
Previously Published as
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR81-472
Type
technical report