Sorting on a mesh-connected parallel computer

Clark D. Thompson, H. T. Kung · Communications of the ACM · 1977

Two algorithms are presented for sorting n 2 elements on an n × n mesh-connected processor array that require O (n) routing and comparison steps. The best previous algoritmhm takes time O(n log n). The algorithms of this paper are shown to be optimal in time within small constant factors. Extensions to higher-dimensional arrays are also given.

Cited by 472 works. doi:10.1145/359461.359481 Open-access PDF

Authors

References