Home → Magazine Archive → April 1977 (Vol. 20, No. 4) → Sorting on a mesh-connected parallel computer → Abstract

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

Save PDF
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


No entries found