zbMATH — the first resource for mathematics

Tight bounds on the complexity of parallel sorting. (English) Zbl 0556.68024
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=\Omega (N^ 2\log^ 2 N);\) and 3) the construction of a ”small-constant-factor” bounded-degree network that sorts N \(\Theta\) (log N)-bit numbers in \(T=\Theta (\log N)\) bit steps with \(A=\Theta (N^ 2)\) area.

68P10 Searching and sorting
68Q25 Analysis of algorithms and problem complexity
68N25 Theory of operating systems
Full Text: DOI