Distributed Sorting

1 April 1985

journal article
Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Computers

Vol. C-34 (4) , 372-376
https://doi.org/10.1109/tc.1985.5009389

Abstract

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.

Keywords

This publication has 9 references indexed in Scilit:

Shout echo selection in distributed files
Networks, 1986
Optimal Distributed Algorithms for Sorting and Ranking
IEEE Transactions on Computers, 1985
Sorting a distributed file in a network
Computer Networks (1976), 1984
On the message complexity of distributed problems
International Journal of Parallel Programming, 1984
The complexity of sorting on distributed systems
Information and Control, 1984
Tradeoffs for selection in distributed networks (Preliminary Version)
Published by Association for Computing Machinery (ACM) ,1983
Distributed k-selection
Published by Association for Computing Machinery (ACM) ,1983
A Distributed Algorithm for Minimum-Weight Spanning Trees
ACM Transactions on Programming Languages and Systems, 1983
Finding the median distributively
Journal of Computer and System Sciences, 1982