×

A new parallel sorting algorithm based upon min-mid-max operations. (English) Zbl 0542.68044

Summary: In this paper we propose a new parallel sorting algorithm which is based upon an operation which sorts three elements. This algorithm is similar to the parallel odd-even merge sorting algorithm proposed by Batcher, except in the latter, the basic operation sorts only two elements. The correctness of our algorithm is also proved.

MSC:

68P10 Searching and sorting
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] M. Aigner,Parallel complexity of sorting problems, J. of Algorithms 3, (1982), pp. 79–88. · Zbl 0547.68061
[2] H. Barlow, D. J. Evans and J. Shanehchi,A parallel merging algorithm, Information Processing Letters 13, No. 3, Dec. 1981, pp. 103–106. · Zbl 0472.68025
[3] K. W. Batcher,Sorting networks and their applications, AFIPS Conf. 32, (1968), pp. 307–314.
[4] G. Baudet and D. Stevenson,Optimal sorting algorithms for parallel computers, IEEE Trans. Comput. C-27, No. 1, Jan. 1978, pp. 84–87. · Zbl 0369.68021
[5] H. K. Brock, B. J. Brooks and F. Sullivan,Diamond, a sorting method for vector machines, BIT 21; 2, (1981), pp. 142–152. · Zbl 0457.68054
[6] T. C. Chen, K. P. Eswaran, V. Y. Lum and C. Tung,Simplified odd-even sort using multiple shift-register loops, IJCIS 7, No. 3, 1978, pp. 293–314. · Zbl 0402.68049
[7] F. Y. Chin and K. S. Fok,Fast sorting algorithms on uniform ladders (multiple shift-register loops), IEEE Trans. Comput. C-27, No. 7, July 1980, pp. 618–631. · Zbl 0436.68040
[8] F. Gavril,Merging with parallel processors, Comm. ACM 18; 10, Oct. 1975, pp. 588–591. · Zbl 0311.68031
[9] R. Haggkvist and P. Hell,Parallel sorting with constant time for comparisons, SIAM J. Comput. 10; 3, Aug. 1981, pp. 465–472. · Zbl 0461.68062
[10] D.S. Hirschberg,Fast parallel sorting algorithms, Comm. ACM 21; 8, Aug. 1978, pp. 657–661. · Zbl 0383.68051
[11] R. W. Hockney and C. R. Jesshope,Parallel Computers, Adam Hilger Ltd., Bristol (1981).
[12] D. E. Knuth,Sorting and Searching, Vol. 3, The Art of Computer Programming, Addison-Wesley, Reading, MA. (1973). · Zbl 0302.68010
[13] 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, No. 3, March 1983. · Zbl 0513.68055
[14] D. J. Kuck,The Structure of Computers and Computations, Vol. 1, (1978), Wiley.
[15] D. T. Lee, H. Chang and C. K. Wong,An on-chip compare/steer bubble sorter, IEEE Trans. Comput. C-27, No. 6, June 1981, pp. 396–404. · Zbl 0456.68066
[16] C. L. Liu,Elements of Discrete Mathematics, (1977), McGraw Hill, New York. · Zbl 0392.00001
[17] D. E. Muller and F. P. Preparata,Bounds to complexities of networks for sorting and for switching, J. Assoc. Comput. Math. 22; 2, April 1975, pp. 195–201. · Zbl 0334.94007
[18] D. Nassimi and S. Sahni,Bitonic sort on a mesh-connected parallel computer, IEEE Trans. Comput. C-27, No. 1, Jan. 1979, pp. 2–7. · Zbl 0388.68058
[19] D. Nassimi and S. Sahni,Parallel permutation and sorting algorithms and a new generalized connection network, J. Assoc. Comput. Math. 29; 3, July 1982, pp. 642–667. · Zbl 0488.68045
[20] F. P. Preparata,Parallelism in sorting, Proc. of 1977 International Conf. on Parallel Processing, pp. 202–206.
[21] F. P. Preparata,New parallel sorting schemes, IEEE Trans. Comput. C-27, No. 7, July 1978, pp. 669–773. · Zbl 0379.68025
[22] R. Reischuk,A fast probabilistic parallel sorting algorithm, IEEE 1981 Symposium on Foundation of Computer Science, pp. 212–219.
[23] Y. Shiloach and U. Vishkin,Finding the maximum, merging, and sorting in a parallel computation model, J. of Algorithms 2, (1981), pp. 88–102. · Zbl 0456.68062
[24] H. S. Stone,Parallel processing perfect shuffle, IEEE Trans. Comput. C-20, Feb. 1971, pp. 153–161. · Zbl 0214.42703
[25] H. S. Stone,Sorting on STAR, IEEE Trans. Software Engineering SE-4, No. 2, Mar. 1978, pp. 138–146. · Zbl 05341293
[26] C. D. Thompson and H. T. Kung,Sorting on a mesh-connected parallel computer, Comm. ACM 20; 4, April 1977, pp. 263–271. · Zbl 0349.68020
[27] S. Todd,Algorithm and hardware for a merge sort using multiple processors, IBM J. Res. Develop. 22; 5, Sep. 1978, pp. 509–517. · Zbl 0382.68057
[28] L. G. Valiant,Parallelism in comparison problems, SIAM J. Comput. 4; 3, Sep. 1975, pp. 348–355. · Zbl 0311.68033
[29] A. C. Yao and F. F. Yao,Lower bounds on merging networks, J. Assoc. Comput. Math. 23; 3, July 1976, pp. 566–571. · Zbl 0335.68034
[30] H. Yasuura, N. Takagi and S. Yajima,The parallel enumeration sorting scheme for VLSI, IEEE Trans. Comput. C-3, No. 12, Dec. 1982, pp. 1192–1201.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.