VECTORIZATION OF SORTING ALGORITHMS

The ability of the existence of vectorizing compilers to extract vector instructions from blocks of sequential code does not remove the need for proper choice of software algorithms. In this paper, we study the vectorization of the insertion sorting, shellsort, and radix sortings. To measure their suitability for vectorization, we have implemented them on a Convex C-l, and computed the scalar/vector speedup for each method. We observed that for sorting methods based on compare/exchange, contingent methods often thought unsuitable for vectorization, the insertion sort is well performed, especially when using an M-section approach. And for radix sortings, the LSD methods are more suited to vectorization compared to the MSD methods. Finally, based on our study and experiments, we suggest that the straight radix sorting is a good choice for use on vector supercomputers.