Optimized Concise Implementation of Batcher's Odd-Even Sorting

摘要

The odd-even sort algorithm designed by Batcher [1] is a divide-and-conquer parallel sorting algorithm with O(log^{2(n)) delay time [2]. It is described in the literature [3] as very practical due to the potentially easy implementation, which is a notable advantage over AKS sorting networks [4]. However, the most basic literature on that topic contains either theoretical background without any implementations usable with the modern compilers [2] or C-like code snippets that are apparently erroneous [3]. In this paper, we propose an alternative to the code from [3] which improves compatibility with the C++ standard [5], fixes the bug that affected the computational complexity, and yields even further practical improvement to the execution time. All the specified enhancements are achieved without increasing the structural complexity of the method, so the proposed code remains as concise as the original.}