Tight Bounds on the Complexity of Parallel Sorting

By Frank Thomson Leighton. 1984

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. Our most important new results are: 1) the construction of an N-node degree-3 network capable of sorting N numbers in O(log N) word steps; 2) a proof that any network capable of sorting N (7 log N)-bit numbers in T bit steps requires area A where AT2 = ¿(N2 log2 N); and 3) the construction of a ``small-constant-factor'' bounded-degree network that sorts N ¿(log N)-bit numbers in T = ¿(log N) bit steps with A = ¿(N2) area.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Prochlo: Strong Privacy for Analytics in the Crowd (2017, methodology): “ColumnSort is a more efficient, data-independent sorting algorithm, improving on Batcher’s sort’s O((log2N)(2)) rounds and sorting datasets in just exactly 8 rounds [44].”
A decomposition for in-place matrix transposition (2014, background): “We are not the first to view transposition in this manner, for example, see the description of Columnsort in Leighton [4], where the C2R permutation is called “transpose”, and the R2C permutation is called “untranspose”.”
Relaxing the problem-size bound for out-of-core columnsort (2003, methodology): “All of these programs are based on Leighton’s 8-step columnsort algorithm [5].”
PROCHLO: Strong Privacy for Analytics in the Crowd (2017, methodology): “ColumnSort is a more efficient, data-independent sorting algorithm, improving on Batcher’s sort’s O((log2N)(2)) rounds and sorting datasets in just exactly 8 rounds [44].”
Opaque: An Oblivious and Encrypted Distributed Analytics Platform (2017, unknown): “Instead, Opaque uses column sort [20], which sorts the data using a fixed number of shuffles (5 in our experiments) by exploiting the fact that a single machine can hold many items.”
The input/output complexity of sorting and related problems (1988, unknown): “The optimal upper bounds for B = 1 when M = N " (l), can be obtained via a recursive application of Columnsort [7] tion, they have derived bounds on the constant factors involved in their version of the problem.”
External memory algorithms and data structures: dealing with massive data (2001, methodology): “A final application of Columnsort [Leighton 1985] suffices to restore total order; partial striping is employed to meet the memory constraints.”