IEEE - Institute of Electrical and Electronics Engineers, Inc. - Tight Bounds on the Complexity of Parallel Sorting

Author(s): Tom Leighton
Sponsor(s): IEEE Comput. Soc. Tech. Committee on Distributed Process
Publisher: IEEE - Institute of Electrical and Electronics Engineers, Inc.
Publication Date: 1 April 1985
Volume: C-34
Page(s): 344 - 354
ISSN (Paper): 0018-9340
DOI: 10.1109/TC.1985.5009385
Regular:

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.... View More

Advertisement