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
- Sorting networks and their applications
- Parallel Processing with the Perfect Shuffle
- The ILLIAC IV Computer
- Very high-speed computing systems
- Some Complexity Results for Matrix Computations on Parallel Processors
- Optimal Sorting Algorithms for Parallel Computers
- Computer organization and algorithms for very-high speed computations.