A logarithmic time sort for linear size networks

ABSTRACT

A randomized algorithm that sorts on an N node network with constant valence in O(log N) time is given. More particularly, the algorithm sorts N items on an N-node cube-connected cycles graph, and, for some constant k, for all large enough &agr;, it terminates within k&agr; log N time with probability at least 1 - N-&agr;.

REFERENCES

• 1: M. Ajtai , J. Komlós , E. Szemerédi, An 0(n log n) sorting network, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.1-9, December 1983 [doi>10.1145/800061.808726]
• 2: R. Aleliunas, Randomized parallel communication (Preliminary Version), Proceedings of the first ACM SIGACT-SIGOPS symposium on Principles of distributed computing, p.60-72, August 18-20, 1982, Ottawa, Canada [doi>10.1145/800220.806683]
• 3: ANGLUIN, D., AND VALIANT, L.G. Fast probabilistic algorithms for Hamiltonian circuits and matchings. J. Comput. Syst. Sci. 18, 2 (1979), 155-193.
• 4: BATCHER, K. Sorting networks and their applications. In AFIPS Spring Joint Computer Conference, vol. 32. AFIPS Press, Reston, Va., 1968, pp. 307-314.
• 5: CHERNOFF, H. A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Ann. Math. Stat. 23 (1952), 493-507.
• 6: ERDOS, P., AND SPENCER, J. Probabilistic Methods in Combinatorics. Academic Press, Orlando, Fla., 1974.
• 7: D. S. Hirschberg, Fast parallel sorting algorithms, Communications of the ACM, v.21 n.8, p.657-661, Aug. 1978 [doi>10.1145/359576.359582]
• 8: HOARE, C. A.R. QUICKSORT. Comput. J. 5, 1 (1962), 10-15.
• 9: HOEFFDING, W. On the distribution of the number of successes in independent trials. Ann. Math. Stat. 27 (1956), 713-721.
• 10: Tom Leighton, Tight bounds on the complexity of parallel sorting, Proceedings of the sixteenth annual ACM symposium on Theory of computing, p.71-80, December 1984 [doi>10.1145/800057.808667]
• 11: David Nassimi , Sartaj Sahni, Parallel permutation and sorting algorithms and a new generalized connection network, Journal of the ACM (JACM), v.29 n.3, p.642-667, July 1982 [doi>10.1145/322326.322329]
• 12: PREPAr~A'rA, F.P. New parallel-sorting schemes. IEEE Trans. Comput. C27, 7 (1978), 669-673.
• 13: Franco P. Preparata , Jean Vuillemin, The cube-connected cycles: a versatile network for parallel computation, Communications of the ACM, v.24 n.5, p.300-309, May 1981 [doi>10.1145/358645.358660]
• 14: RAmN, M.O. Probabilistic algorithms. In Algorithms and Complexity, J. F. Traub, Ed. Academic Press, Orlando, Fla., 1976.
• 15: REtSCrtt~K, R. A fast probabilistic parallel sorting algorithm. In Procedings of the 22nd IEEE Symposium on Foundations of Computer Science. IEEE, New York, 1981, pp. 212-219.
• 16: SOLOVAV, R., AND STRASSEN, V. A fast Monte-Carlo test for primality. SlAM J. Comput. 6 (1977), 84-85.
• 17: Jeffrey D Ullma, Computational Aspects of VLSI, W. H. Freeman & Co., New York, NY, 1984
• 18: Eli Upfal, Efficient schemes for parallel communication, Proceedings of the first ACM SIGACT-SIGOPS symposium on Principles of distributed computing, p.55-59, August 18-20, 1982, Ottawa, Canada [doi>10.1145/800220.806682]
• 19: VALIANT, L. G. A scheme for fast parallel communication. SlAM J. Comput. 11, 2 (1982), 350-361.
• 20: L. G. Valiant , G. J. Brebner, Universal schemes for parallel communication, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.263-277, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802479]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY

General Terms:
Algorithms, Design, Performance, Theory, Verification