OPTIMAL SIMD-EREW PARALLEL SORTING ALGORITHMS
Yin Xin-chun · Journal of Yangzhou University · 2002
Optimal parallel sorting algorithms on SIMDEREW are presented. To avoid memory access conflict, the algorithms are based on a parallel merge algorithm. For a sequence with n elements, the time complexity of the algorithms is O(n 1-e lb n) if processed on n e processors. The cost is O(n lb n) which is optimal for sorting and the parallel algorithm is self-adapting.