Sorting on a mesh-connected parallel computer

By C. D. Thompson, H. T. Kung

Communications of the ACM, Vol. 20 No. 4, Pages 263-271
10.1145/359461.359481

Two algorithms are presented for sorting n2 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.

The full text of this article is premium content

0 Comments

No entries found

Purchase the Article

Sorting on a mesh-connected parallel computer

The full text of this article is premium content

0 Comments

Forgot your password?

Need Access?

Join the ACM

Subscribe to Communications of the ACM Magazine