AN EFFICIENT IMPLEMENTATION AND PERFORMANCE ANALYSIS OF PARALLEL BITONIC SORTING

Sorting is one of the most common operations performed by a computer. The very famous bitonic sorting is one of the earliest parallel sorting algorithms. Bitonic sorting has a very important impact on the research of parallel sorting algorithms. Many parallel sorting algorithms are based on bitonic sorting. Following the basic strategy of bitonic sorting, here given is an efficient implementation scheme of bitonic sorting on a distributed memory parallel machine. To solve the communication problem in bitonic sorting, local all-to-all communication patterns are used instead of total exchanges. The computational complexity of the algorithm isΘ（n/p（logn+log2p））, wheren is the number of keys to be sorted, andp is the number of processors. The communication complexity of the algorithm on a 2-D mesh isO（2 12132p·n/p）. The order of this communication complexity reaches the theoretical lower bound.The analytical result shows that the communication performance and the scalability of bitonic sorting are excellent.