The Complexity of Sorting on Distributed Systems.
ILLINOIS UNIV AT URBANA APPLIED COMPUTATION THEORY GROUP
Pagination or Media Count:
The sorting problem is no arrange N values in a distributed system of N processors into sorted order. Let the values be in 0,...,L. Every sorting algorithm requires omega N 2 lgLNlg N messages on a bidirectional ring with N processors. Every sorting algorithm requires omega N 32 lgLNlg N messages on a square mesh with N processors. A novel sorting algorithm for unidirectional rings achieves the first lower bound. Author
- Computer Hardware
- Computer Systems
- Non-Radio Communications