Sorting on a mesh-connected parallel computer

ABSTRACT

Two algorithms for sorting n2 elements on an n×n mesh-connected processor array that require 0(n) routing and comparison steps are presented. The best previous algorithms take time 0(n log n). Our algorithms are shown to be optimal in time within small constant factors.

REFERENCES

• 1: Barnes, G. H., et. al {1968}. "The ILLIAC IV Computer," IEEE Trans. on Computers, C-17, pp. 746-757.
• 2: Batcher, K. E. {1968}. "Sorting Networks and Their Applications," Proc. AFIPS Spring Joint Computer Conference, Vol. 32, pp. 307-314.
• 3: Baudet, G., and Stevenson, D. {1975}. "Optimal Sorting Algorithms for Parallel Computers", Computer Science Department report, Carnegie-Mellon University, May 1975.
• 4: Flynn, M. J. {1966}. "Very High-Speed Computing Systems," Proc. IEEE, Vol.54, pp. 1901-1909.
• 5: Donald E. Knuth, The art of computer programming, volume 3: (2nd ed.) sorting and searching, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1998
• 6: Samuel Ellis Orcutt, Jr., Computer organization and algorithms for very-high speed computations., 1975
• 7: Stone, H. S. {1971}. "Parallel Processing with the Perfect Shuffle," IEEE Trans. on Computers, Vol. C-20, pp. 153-161.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

General Terms:
Algorithms