%0 Conference Paper %1 leighton84 %A Leighton, Tom %B Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing %C New York, NY, USA %D 1984 %I ACM %K algorithm complexity parallel sorting %P 71--80 %R 10.1145/800057.808667 %T Tight Bounds on the Complexity of Parallel Sorting %X In this paper, we prove tight upper and lower bounds on the number or 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 O(N))-node bounded-degree 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≥ &Ohgr;(N2log2N), and 3) the construction of a “small-constant-factor” bounded-degree network that sorts $N \Theta(N)$-bit numbers in T &equil; &thgr;(log N) bit steps with A &equil; &thgr;(N2) area. %@ 0-89791-133-4

@inproceedings{leighton84, abstract = {In this paper, we prove tight upper and lower bounds on the number or 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 O(N))-node bounded-degree 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≥ &Ohgr;(N2log2N), and 3) the construction of a “small-constant-factor” bounded-degree network that sorts $N \Theta(\log N)$-bit numbers in T &equil; &thgr;(log N) bit steps with A &equil; &thgr;(N2) area.}, acmid = {808667}, added-at = {2016-11-05T11:19:50.000+0100}, address = {New York, NY, USA}, author = {Leighton, Tom}, biburl = {https://www.bibsonomy.org/bibtex/2029c0a29142559a20bb2b091a09d982c/ytyoun}, booktitle = {Proceedings of the Sixteenth Annual ACM Symposium on Theory of Computing}, doi = {10.1145/800057.808667}, interhash = {056d23e1789b92b43bc949793c02a895}, intrahash = {029c0a29142559a20bb2b091a09d982c}, isbn = {0-89791-133-4}, keywords = {algorithm complexity parallel sorting}, numpages = {10}, pages = {71--80}, publisher = {ACM}, series = {STOC '84}, timestamp = {2016-11-06T09:00:55.000+0100}, title = {Tight Bounds on the Complexity of Parallel Sorting}, year = 1984 }