article · IEEE Transactions on Computers · 1985

Tight Bounds on the Complexity of Parallel Sorting

Cited by 372Abstract and details only

Abstract

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.

Cite this paper

APA 7

Leighton, T. (1985). Tight Bounds on the Complexity of Parallel Sorting. IEEE Transactions on Computers, C-34(4), 344–354. https://doi.org/10.1109/tc.1985.5009385

MLA 9

Leighton, Tom. “Tight Bounds on the Complexity of Parallel Sorting.” IEEE Transactions on Computers, vol. C-34, no. 4, 1985, pp. 344–54, https://doi.org/10.1109/tc.1985.5009385.

Chicago

Leighton, Tom. 1985. “Tight Bounds on the Complexity of Parallel Sorting.” IEEE Transactions on Computers C-34 (4): 344–54. https://doi.org/10.1109/tc.1985.5009385.

Harvard

Leighton, T. (1985) ‘Tight Bounds on the Complexity of Parallel Sorting’, IEEE Transactions on Computers, C-34(4), pp. 344–354. Available at: https://doi.org/10.1109/tc.1985.5009385.

BibTeX

@article{leighton1985tight,
  title = {{Tight Bounds on the Complexity of Parallel Sorting}},
  author = {Leighton, Tom},
  journal = {IEEE Transactions on Computers},
  volume = {C-34},
  number = {4},
  pages = {344--354},
  year = {1985},
  doi = {10.1109/tc.1985.5009385}
}

Made from the index record. Check names, capitalisation and page numbers against the paper. Need another style? AI for Research has over 10,000.