Distributed Sorting
Doron Rotem, Nicola Santoro, Jeffrey B. Sidney · IEEE Transactions on Computers · 1985
The problem of sorting a file distributed over a number of sites of a communication network is examined. Two versions of this problem are investigated; distributed solution algorithms are presented; and their communication complexity analyzed both in the worst and in the average case. The worst case bounds are shown to be sharp, with respect to order of magnitude, for large files.