Tight Bounds on the Complexity of Parallel Sorting

摘要

In this paper, we prove tight upper and lower bounds on the number of processors, information transfer, wire area and time needed to sort N numbers in a bounded-degree fixed-connection network.