VECTORIZATION OF SORTING ALGORITHMS

作     者：CHUNG-PING CHUNG WEN-YANG LIN 

作者机构：Institute of Computer Science and Information Engineering College of Engineering National Chiao Tung University Hsinchu Taiwan 30050 R.O.C. 

出 版 物：《International Journal of High Speed Computing》 

年 卷 期：1992年第4卷第3期

页      面：213-232页

主　　题：Vectorization sorting algorithm insertion sort M-section radix sort 

摘      要：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.