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.
Similar content being viewed by others
References
K. E. Batcher, Sorting Networks and Their Applications,AFIPS Conf.,32:307–314 (1968).
H. S. Stone, Parallel Processing Perfect Shuffle,IEEE Trans. Comput.,C-20:153–161 (February 1971).
R. L. Drysdale and F. H. Young, Improved Divide/Sort/Merge Sorting Network,SIAM J. Comput.,4(3):264–270 (September 1975).
F. Gavril, Merging with Parallel Processors,Comm. ACM,18(10):588–591 (October 1975).
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).
L. G. Valiant, Parallelism in Comparison ProblemsSIAM J. Comput.,4 (3):348–355 (September 1975).
A. C. Yao and F. F. Yao, Lower Bounds on Merging Networks,J. Assoc. Comput. Math.,23(3):566–571 (July 1976).
F. P. Preparata, Parallelism in Sorting,Proc. of Intl. Conf. on Parallel Processing, pp. 202–206.
C. D. Thompson and H. T. Kung, Sorting on a Mesh-Connected Parallel Computer,Comm. ACM,20(4):263–271 (April 1977).
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).
D. S. Hirschberg, Fast Parallel Sorting Algorithms,Comm. ACM,21(8):657–661 (August 1978).
F. P. Preparata, New Parallel Sorting Schemes,IEEE Trans. Comput.,C-27(7):669–773 (July 1978).
G. Baudet and D. Stevenson, Optimal Sorting Algorithms for Parallel Computers,IEEE Trans. Comput.,C-27(1):84–87 (January 1978).
H. S. Stone, Sorting on STAR,IEEE Trans. Software Engineering,SE-4, (2):138–146 (March 1978).
S. Todd, Algorithm and Hardware for a Merge Sort Using Multiple Processors,IBM J. Res. Develop.,22(5):509–517 (September 1978).
D. Nassimi and S. Sahni, Bitonic Sort on a Mesh-Connected Parallel Computer,IEEE Trans. Comput.,C-27(1):2–7 (January 1979).
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).
H. Barlow, D. J. Evans and J. Shanehchi, A Parallel Merging Algorithm,Infor. Proc. Letters, Vol.13(3):103–106 (December 1981).
R. Haggkvist and P. Hell, Parallel Sorting with Constant Time for Comparisons,SIAM J. COMPUT.,10(3):465–472 (August 1981).
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).
Y. Shiloach and U. Vishkin, Finding the Maximum, Merging, and Sorting in a Parallel Computation Model,J. of Algorithms 2:88–102 (1981).
M. Aigner, Parallel Complexity of Sorting Problems,J. of Algorithms 3:79–88 (1982).
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).
H. Yasuura, N. Takagi, and S. Yajima, The Parallel Enumeration Sorting Scheme for VLSI,IEEE Trans. Comput.,C-31(12):1192–1201 (December 1982).
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).
S. S. Tseng and R. C. T. Lee, A New Parallel Sorting Algorithm Based Upon Min-Mid-Max Operations,BIT,24:187–195 (1984).
S. S. Tseng,Parallel Sorting Algorithms, Ph. D. Dissertation, National Chiao Tung University, Hsinchu, Taiwan, Republic of China (May 1984).
R. Reischuk, A Fast Probabilistic Parallel Sorting Algorithm,IEEE Symp. on Found. of Comput. Sci., pp. 212–219 (1981).
H. K. Brock, B. J. Brooks, and F. Sullivan, Diamond, a Sorting Method for Vector Machines,BIT,21(2):142–152 (1981).
Author information
Authors and Affiliations
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
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
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF00991185