A logarithmic time sort for linear size networks

ABSTRACT

We give a randomized algorithm that sorts on an N node network with constant valence in 0(log N) time. 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: 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]
• 2: D. Angluin and L.G. Valiant. Fast probabilistic algorithms for Hamiltonian circuits and matchings. J. of Comp. and Syst. Sci. (1979), 155-193.
• 3: K. Batcher. Sorting networks and their applications. AFIPS Spring Joint Comp. Conf. 32 (1968), 307-314.
• 4: H. Chernoff. A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. Ann. of Math. Stat.23 (1952), 493-507.
• 5: P. Erdös and J. Spencer. Probabilistic Methods in Combinatorics. Academic Press (1974).
• 6: C.A.R. Hoare. QUICKSORT. Computer J.5(1), (1962), 10-15.
• 7: W. Hoeffding. On the distribution of the number of successes in independent trials. Ann.of Math. Stat.27 (1956), 713-721.
• 8: 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]
• 9: 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]
• 10: M.O. Rabin. Probabilistic algorithms. In Algorithms and Complexity. J.F. Traub (ed.), Academic Press, New York, 1976.
• 11: R. Reischuk. A fast probabilistic parallel sorting algorithm. Proc. of 22nd IEEE Symp. on Foundations of Computer Science (1981), 212-219.
• 12: R. Solovay and V. Strassen. A fast Monte-Carlo test for primality. SIAM J. on Computing6,(1977), 84-85.
• 13: 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]
• 14: L.G. Valiant. A scheme for fast parallel communication. SIAM J. on Computing11:2 (1982), 350-361.
• 15: 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:
  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Network problems

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.3 Complexity Measures and Classes
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Sorting and searching

General Terms:
Algorithms, Theory