About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Journal of Algorithms
Paper
Cubesort: A parallel algorithm for sorting N data items with S-sorters
Abstract
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.