C. Bernard Shung, Horng-Dar Lin, et al.
IEEE Transactions on Communications
This paper presents a parallel sorting algorithm called Cubesort. Cubesort sorts N data items by performing a number of rounds, each of which partitions the N data items into groups of size S and sorts within the groups. For many values of N and S, Cubesort requires fewer such rounds than are required by any previously published algorithm. Cubesort can also be used to sort N data items on hypercube, shuffle-exchange, and cube-connected cycles computers with P processors in time O(N log2 N P log( N P)) over a wide range of the parameters N and P. In particular, when N = P1 + 1 k and k is a constant, Cubesort sorts on the above parallel computers in O(N log N P) time, thus obtaining an optimal processor-time product for comparison sorting. The application of Cubesort to general routing problems is also discussed. © 1992.
C. Bernard Shung, Horng-Dar Lin, et al.
IEEE Transactions on Communications
Jehoshua Bruck, Robert Cypher, et al.
SPDP 1992
Vasanth Bala, Jehoshua Bruck, et al.
IEEE TPDS
Jehoshua Bruck, Robert Cypher, et al.
SIAM Journal on Computing