An optimized bitonic sorting strategy with midpoint-based dynamic communication

• Optimized Bitonic Sort (OBS) is proposed to improve complexity and sorting time.
• Using midpoint-weight key in OBS can reduce logP(logP+1)/2logP(logP+1)/2 to 1,2,3,…1,2,3,…, or logPlogP iterations.
• A good key in PE-ranking can find the right place for (Pi,Pj)(Pi,Pj) communication.
• Correctness and complexity analysis of OBS have been proved.
• Experimental results of OBS outperform those of the best of existing method 35%–54%.

This paper proposes an optimized Bitonic sorting (OBS) strategy with midpoint-based dynamic communication. Our OBS strategy uses the midpoint-weight list ranking to improve complexity and reduce time of sorting on parallel and distributed systems. Applying a better key in the PE  -list ranking can find the right place of (PiPi, PjPj) and improve communication time significantly (i.e., fewer iterations, better synchronization in each iteration, faster convergence to the result), while most of coarse-grain parallel sorting (P