Complexity of Sorting on Distributed Systems

摘要

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 lg(L/N)/lg N) messages on a bidirectional ring with N processors. Every sorting algorithm requires omega (N 3/2 lg(L/N)/lg N) messages on a square mesh with N processors. A novel sorting algorithm for unidirectional rings achieves the first lower bound. (Author)