The periodic balanced sorting network

ABSTRACT

A periodic sorting network consists of a sequence of identical blocks. In this paper, the periodic balanced sorting network, which consists of log n blocks, is introduced. Each block, called a balanced merging block, merges elements on the even input lines with those on the odd input lines. The periodic balanced sorting network sorts n items in O([log n]2) time using (n/2)(log n)2 comparators. Although these bounds are comparable to many existing sorting networks, the periodic structure enables a hardware implementation consisting of only one block with the output of the block recycled back as input until the output is sorted. An implementation of our network on the shuffle exchange interconnection model in which the direction of the comparators are all identical and fixed is also presented.

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: BATCHER, K. Sorting networks and their applications. In AFIPS Spring Joint Computer Conference, vol. 32, 1968, pp. 307-314.
• 3: BILARDI, G. A family of merging networks derived from the bitonic merger. In Proceedings of the 23rd Allerton Conference on Communication, Control, and Computing. University of Illinois, Urbana-Champaign, Ill., 1985, pp. 261-267.
• 4: HOARE, C. A.R. Quicksort. Comput. J. 5 (i962), i0-i5.
• 5: Zhu Hong , Robert Sedgewick, Notes on merging networks (Prelimiary Version), Proceedings of the fourteenth annual ACM symposium on Theory of computing, p.296-302, May 05-07, 1982, San Francisco, California, United States [doi>10.1145/800070.802204]
• 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: C. P. Kruskal , M. Snir, A Unified theory of interconnection network structure, Theoretical Computer Science, v.48 n.1, p.75-94, Dec., 1986
• 8: LAWRIE, D.H. Access and alignment of data in an array processor. IEEE Trans. Comput. C-24 (!975), !!45-! !55.
• 9: Y. Perl, Better understanding of Batcher's merging networks, Discrete Applied Mathematics, v.25 n.3, p.257-271, Nov. 1989 [doi>10.1016/0166-218X(89)90004-8]
• 10: John H. Reif , Leslie G. Valiant, A logarithmic time sort for linear size networks, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.10-16, December 1983 [doi>10.1145/800061.808727]
• 11: RUDOLPH, L. A robust sorting network. IEEE Trans. Comput. C-32, 4 (Apr. 1985), 326-335.
• 12: Jacob T. Schwartz, Ultracomputers, ACM Transactions on Programming Languages and Systems (TOPLAS), v.2 n.4, p.484-521, Oct. 1980 [doi>10.1145/357114.357116]
• 13: D. L. Shell, A high-speed sorting procedure, Communications of the ACM, v.2 n.7, p.30-32, July 1959 [doi>10.1145/368370.368387]
• 14: STONE, H.S. Parallel processing with the perfect shuffle. IEEE Trans. Comput. C-20, 2 (Feb. 1971), 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

Additional Classification:
  F. Theory of Computation
  F.1 COMPUTATION BY ABSTRACT DEVICES
      F.1.1 Models of Computation
          Subjects: Unbounded-action devices (e.g., cellular automata, circuits, networks of machines)

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.1 Combinatorics
          Subjects: Combinatorial algorithms; Permutations and combinations; Recurrences and difference equations

General Terms:
Algorithms, Design, Theory