Skip to main content
Springer Nature Link
Log in

A parallel sorting scheme whose basic operation sortsN elements

  • Published:
International Journal of Computer & Information Sciences Aims and scope Submit manuscript

Abstract

Batcher proposed a parallel sorting scheme whose basic operation sorts two elements. Tseng and Lee extended his results. They proposed a parallel sorting scheme whose basic operation sorts three elements. In this paper, we propose a parallel sorting scheme whose basic operation sortsn elements wheren is an arbitrary number. The correctness of this algorithm is given.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. K. E. Batcher, Sorting Networks and Their Applications,AFIPS Conf.,32:307–314 (1968).

    Google Scholar 

  2. H. S. Stone, Parallel Processing Perfect Shuffle,IEEE Trans. Comput.,C-20:153–161 (February 1971).

    Google Scholar 

  3. R. L. Drysdale and F. H. Young, Improved Divide/Sort/Merge Sorting Network,SIAM J. Comput.,4(3):264–270 (September 1975).

    Google Scholar 

  4. F. Gavril, Merging with Parallel Processors,Comm. ACM,18(10):588–591 (October 1975).

    Google Scholar 

  5. D. E. Muller and F. P. Preparata, Bounds to Complexities of Networks for Sorting and for Switching,J. Assoc. Comput. Math.,22(2):195–201 (April 1975).

    Google Scholar 

  6. L. G. Valiant, Parallelism in Comparison ProblemsSIAM J. Comput.,4 (3):348–355 (September 1975).

    Google Scholar 

  7. A. C. Yao and F. F. Yao, Lower Bounds on Merging Networks,J. Assoc. Comput. Math.,23(3):566–571 (July 1976).

    Google Scholar 

  8. F. P. Preparata, Parallelism in Sorting,Proc. of Intl. Conf. on Parallel Processing, pp. 202–206.

  9. C. D. Thompson and H. T. Kung, Sorting on a Mesh-Connected Parallel Computer,Comm. ACM,20(4):263–271 (April 1977).

    Google Scholar 

  10. T. C. Chen, K. P. Eswaran, V. Y. Lum, and C. Tung, Simplified Odd-Even Sort Using Multiple Shift-Register Loops,IJCIS,7(3):293–314 (1978).

    Google Scholar 

  11. D. S. Hirschberg, Fast Parallel Sorting Algorithms,Comm. ACM,21(8):657–661 (August 1978).

    Google Scholar 

  12. F. P. Preparata, New Parallel Sorting Schemes,IEEE Trans. Comput.,C-27(7):669–773 (July 1978).

    Google Scholar 

  13. G. Baudet and D. Stevenson, Optimal Sorting Algorithms for Parallel Computers,IEEE Trans. Comput.,C-27(1):84–87 (January 1978).

    Google Scholar 

  14. H. S. Stone, Sorting on STAR,IEEE Trans. Software Engineering,SE-4, (2):138–146 (March 1978).

    Google Scholar 

  15. S. Todd, Algorithm and Hardware for a Merge Sort Using Multiple Processors,IBM J. Res. Develop.,22(5):509–517 (September 1978).

    Google Scholar 

  16. D. Nassimi and S. Sahni, Bitonic Sort on a Mesh-Connected Parallel Computer,IEEE Trans. Comput.,C-27(1):2–7 (January 1979).

    Google Scholar 

  17. F. Y. Chin and K. S. Fok, Fast Sorting Algorithms on Uniform Ladders (Multiple Shift-Refister Loops),IEEE Trans. Comput.,C-27(7):618–631 (July 1980).

    Google Scholar 

  18. H. Barlow, D. J. Evans and J. Shanehchi, A Parallel Merging Algorithm,Infor. Proc. Letters, Vol.13(3):103–106 (December 1981).

    Google Scholar 

  19. R. Haggkvist and P. Hell, Parallel Sorting with Constant Time for Comparisons,SIAM J. COMPUT.,10(3):465–472 (August 1981).

    Google Scholar 

  20. D. T. Lee, H. Chang and C. K. Wong, An On-Chip Compare/Steer Bubble Sorter,IEEE Trans. Comput.,C-27, (6):396–404 (June 1981).

    Google Scholar 

  21. Y. Shiloach and U. Vishkin, Finding the Maximum, Merging, and Sorting in a Parallel Computation Model,J. of Algorithms 2:88–102 (1981).

    Google Scholar 

  22. M. Aigner, Parallel Complexity of Sorting Problems,J. of Algorithms 3:79–88 (1982).

    Google Scholar 

  23. D. Nassimi and S. Sahni, Parallel Permutation and Sorting Algorithms and a New Generalized Connection Network,J. Assoc. Comput. Math.,29(3):642–667 (July 1982).

    Google Scholar 

  24. H. Yasuura, N. Takagi, and S. Yajima, The Parallel Enumeration Sorting Scheme for VLSI,IEEE Trans. Comput.,C-31(12):1192–1201 (December 1982).

    Google Scholar 

  25. M. Kumar and D. S. Hirschberg, An Efficient Implementation of Batcher's Odd-Even Merge Algorithm and Its Application in Parallel Sorting Schemes,IEEE Trans. Comput.,C-32(3) (March 1983).

  26. S. S. Tseng and R. C. T. Lee, A New Parallel Sorting Algorithm Based Upon Min-Mid-Max Operations,BIT,24:187–195 (1984).

    Google Scholar 

  27. S. S. Tseng,Parallel Sorting Algorithms, Ph. D. Dissertation, National Chiao Tung University, Hsinchu, Taiwan, Republic of China (May 1984).

    Google Scholar 

  28. R. Reischuk, A Fast Probabilistic Parallel Sorting Algorithm,IEEE Symp. on Found. of Comput. Sci., pp. 212–219 (1981).

  29. H. K. Brock, B. J. Brooks, and F. Sullivan, Diamond, a Sorting Method for Vector Machines,BIT,21(2):142–152 (1981).

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Institute of Computer Engineering, National Chiao Tung University, 300, Hsinchu, Taiwan, Republic of China

    S. S. Tseng

  2. Department of Electrical Engineering, and Institute of Computer and Decision Sciences, National Tsing Hua University, 300, Hsinchu, Taiwan, Republic of China

    R. C. T. Lee

Authors
  1. S. S. Tseng
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. R. C. T. Lee
    View author publications

    You can also search for this author in PubMed Google Scholar

Additional information

This research was partially supported by the National Science Council of the Republic of China under the Contract NSC-73-0201-E-007-01.

Rights and permissions

Reprints and permissions

About this article

Cite this article

Tseng, S.S., Lee, R.C.T. A parallel sorting scheme whose basic operation sortsN elements. International Journal of Computer and Information Sciences 14, 455–467 (1985). https://doi.org/10.1007/BF00991185

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF00991185

Keywords

Search

Navigation