Fast parallel sorting algorithms

ABSTRACT

A parallel bucket-sort algorithm is presented that requires time O(log n) and the use of n processors. The algorithm makes use of a technique that requires more space than the product of processors and time. A realistic model is used in which no memory contention is permitted. A procedure is also presented to sort n numbers in time O(k log n) using n1+1/k processors, for k an arbitrary integer. The model of computation for this procedure permits simultaneous fetches from the same memory location.

REFERENCES

• 1: Alfred V. Aho , John E. Hopcroft, The Design and Analysis of Computer Algorithms, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1974
• 2: Eshrat Arjomandi, A study of parallelism in graph theory., 1976
• 3: Batcher, K.E. Sorting networks and their applications. Proc. AFIPS 1968 SJCC, Vol. 32, AFIPS Press, Montvale, N.J., pp. 307-314.
• 4: Richard P. Brent, The Parallel Evaluation of General Arithmetic Expressions, Journal of the ACM (JACM), v.21 n.2, p.201-206, April 1974 [doi>10.1145/321812.321815]
• 5: Csansky, L. Fast parallel matrix inversion algorithms. Proc. 16th Annual Symp. on Foundations of Comptr. Sci., IEEE, Berkeley, Calif., Oct. 1975, pp. 11-12.
• 6: Shimon Even, Parallelism in tape-sorting, Communications of the ACM, v.17 n.4, p.202-204, April 1974 [doi>10.1145/360924.360941]
• 7: Flynn, M.J. Very high-speed computing systems, Proc. IEEE 54 (Dec. 1966), 1901-1909.
• 8: Fănică Gavril, Merging with parallel processors, Communications of the ACM, v.18 n.10, p.588-591, Oct. 1975 [doi>10.1145/361020.361216]
• 9: D. S. Hirschberg, Parallel algorithms for the transitive closure and the connected component problems, Proceedings of the eighth annual ACM symposium on Theory of computing, p.55-57, May 03-05, 1976, Hershey, Pennsylvania, United States [doi>10.1145/800113.803631]
• 10: Donald E. Knuth, The art of computer programming, volume 1 (3rd ed.): fundamental algorithms, Addison Wesley Longman Publishing Co., Inc., Redwood City, CA, 1997
• 11: 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
• 12: K. N. Levitt , W. H. Kautz, Cellular arrays for the solution of graph problems, Communications of the ACM, v.15 n.9, p.789-801, Sept. 1972 [doi>10.1145/361573.361576]
• 13: David E. Muller , Franco P. Preparata, Bounds to Complexities of Networks for Sorting and for Switching, Journal of the ACM (JACM), v.22 n.2, p.195-201, April 1975 [doi>10.1145/321879.321882]
• 14: Munro, I., and Paterson, M. Optimal algorithms for parallel polynomial evaluation, J. Comptr. Syst. Sci. 7 (1973), 189-198.
• 15: Yoichi Muraoka , David J. Kuck, On the time required for a sequence of matrix products, Communications of the ACM, v.16 n.1, p.22-26, Jan. 1973 [doi>10.1145/361932.361938]
• 16: Stone, H.S. Parallel processing with the perfect shuffle. IEEE Trans. Comptrs. C-20 (1971), 153-161.
• 17: C. D. Thompson , H. T. Kung, Sorting on a mesh-connected parallel computer, Proceedings of the eighth annual ACM symposium on Theory of computing, p.58-64, May 03-05, 1976, Hershey, Pennsylvania, United States [doi>10.1145/800113.803632]
• 18: Valiant, L.G. Parallelism in comparison problems. SIAM J. Comping. 4, 3 (Sept. 1975), 348-355.

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

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES

  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.2 Modes of Computation
          Subjects: Parallelism and concurrency

General Terms:
Algorithms, Design, Performance, Theory

Keywords:
algorithms, bucket sort, parallel processing, sorting