A hypercubic sorting network with nearly logarithmic depth

ABSTRACT

A natural class of “hypercubic” sorting networks is defined. The regular structure of these sorting networks allows for elegant and efficient implementations on any of the so-called hypercubic networks (e.g., the hypercube, shuffle-exchange, butterfly, and cube-connected cycles). This class of sorting networks contains Batcher's O(lg2 n)-depth bitonic sort, but not the O(lg n)-depth sorting network of Ajtai, Komlo´s, and Szemere´di. In fact, no o(lg2 n)-depth compare-interchange sort was previously known for any of the hypercubic networks. In this paper, we prove the existence of a family of 2O((lg lg n)1/2) lg n-depth hypercubic sorting networks. Note that this depth is o(lg1+&egr; n) for any constant &egr; > 0.

REFERENCES

• 1: M. Ajtai , J. Komlós , E. Szemerédi, Sorting in c log n parallel steps, Combinatorica, v.3 n.1, p.1-19, Jan. 1983 [doi>10.1007/BF02579338]
• 2: K. E. Batcher. Sorting networks and their applications. In Proceedings of the AFIPS Spring Joint Computer Conference, vol. 32, pages 307-314, 1968.
• 3: V. E. Bene#. Optimal rearrangeable multistage connecting networks. Bell System Technical Journal, 43:1641-1656, 1964.
• 4: V. Chv~tal. Personal communication.
• 5: R. E. Cypher. Theoretical aspects of VLSI pin limitations. Technical Report RJTl15, IBM Almaden Research Center, November 1989.
• 6: 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
• 7: F. T. Leighton and C. G. Plaxton. A (fairly) simple circuit that (usually) sorts. In Proceedings of the 31st Annual IEEE Symposium on Foundations of Computer Science, pages 264-274, October 1990.
• 8: M. S. Paterson. Improved sorting networks with O(logn) depth. Algorithmica, 5:75-92, 1990.
• 9: C. G Plaxton , Torsten Suel, A Lower Bound for Sorting Networks Based on the Shuffle Permutation, University of Texas at Austin, Austin, TX, 1992

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:
  B. Hardware
  B.6 LOGIC DESIGN
      B.6.1 Design Styles
          Subjects: Combinational logic

General Terms:
Algorithms, Theory