Deterministic sorting in nearly logarithmic time on the hypercube and related computers
作者： R. Cypher , C. G. Plaxton
关键词:
摘要: Abstract This paper presents a deterministic sorting algorithm, called Sharesort, that sorts n records on an -processor hypercube, shuffle-exchange, or cube-connected cycles in O (log log ) 2 time the worst case. The algorithm requires only constant amount of storage at each processor. fastest previous for this problem was Batcher's bitonic sort, which runs time.
acm.org
sci-hub.se 参考文章(19)
Robert Cypher, Theoretical aspects of VLSI pin limitations conference on advanced research in vlsi. pp. 314- 327 ,(1990)
M. Ajtai, J. Komlós, E. Szemerédi, Sorting inc logn parallel steps Combinatorica. ,vol. 3, pp. 1- 19 ,(1983) , 10.1007/BF02579338
David Nassimi, Sartaj Sahni, Data broadcasting in SIMD computers IEEE Transactions on Computers. ,vol. 30, pp. 101- 107 ,(1981) , 10.1109/TC.1981.6312172
H.S. Stone, Parallel Processing with the Perfect Shuffle IEEE Transactions on Computers. ,vol. C-20, pp. 153- 161 ,(1971) , 10.1109/T-C.1971.223205
John H. Reif, Leslie G. Valiant, A logarithmic time sort for linear size networks Journal of the ACM. ,vol. 34, pp. 60- 76 ,(1987) , 10.1145/7531.7532
Nassimi, Sahni, Parallel Algorithms to Set Up the Benes Permutation Network IEEE Transactions on Computers. ,vol. 31, pp. 148- 154 ,(1982) , 10.1109/TC.1982.1675960
Nassimi, Sahni, A Self-Routing Benes Network and Parallel Permutation Algorithms IEEE Transactions on Computers. ,vol. 30, pp. 332- 340 ,(1981) , 10.1109/TC.1981.1675791
David Nassimi, Sartaj Sahni, Parallel permutation and sorting algorithms and a new generalized connection network Journal of the ACM. ,vol. 29, pp. 642- 667 ,(1982) , 10.1145/322326.322329
A. N. Kolmogorov, M. A. Lavrentʹev, Aleksandr Danilovich Aleksandrov, Mathematics : its content, methods, and meaning micm. ,(1963)
Richard Cole, Chee K. Yap, A parallel median algorithm Information Processing Letters. ,vol. 20, pp. 137- 139 ,(1985) , 10.1016/0020-0190(85)90080-8