Answers are grounded in this paper and cite their sources.
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 AT 2 = Ω(N 2 log 2 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 = Θ(N 2 ) area.
No takes yet. Share an insight, caveat, or question.
Tom Leighton (1985) studied this question.
Synapse has enriched 10 related papers. Consider them for comparative context: