Cubesort: A parallel algorithm for sorting N data items with S-sorters

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.