Standardized parallel sorting on SIMD array processor

We present the standardized parallel sorting algorithm. Instead of the most basic CCI (compare and conditional interchange) operation in traditional sorting algorithms, this algorithm compares sorting data with a standard value sequence simultaneously and synchronously on an SIMD array processor. The algorithm possesses three significant advantages. First, the running time T is independent of the problem size, T=0(1). The second attractive feature of the algorithm is that it is not necessary to build a communication network between PEs. Finally, no bottleneck occurs in output. We have implemented the algorithm in an SIMD array processor that is designed by our research group. The experiment verifies all the theoretical predictions. For these merits the algorithm is of significance in both theory and practice. >