Batcher's odd–even mergesort is a generic construction devised by Ken Batcher for sorting networks of size O(n (log n)2) and depth O((log n)2), where n is the number of items to be sorted. Although it is not asymptotically optimal, Knuth concluded in 1998, with respect to the AKS network that "Batcher's method is much better, unless n exceeds the total memory capacity of all computers on earth!"
|Worst-case performance||parallel time|
|Best-case performance||parallel time|
|Average performance||parallel time|
|Worst-case space complexity||non-parallel time|
Various recursive and iterative schemes are possible to calculate the indices of the elements to be compared and sorted. This is one iterative technique to generate the indices for sorting n elements:
# note: the input sequence is indexed from 0 to (n-1) for p = 1, 2, 4, 8, ... # as long as p < n for k = p, p/2, p/4, p/8, ... # as long as k >= 1 for j = mod(k,p) to (n-1-k) with a step size of 2k for i = 0 to min(k-1, n-j-k-1) with a step size of 1 if floor((i+j) / (p*2)) == floor((i+j+k) / (p*2)) compare and sort elements (i+j) and (i+j+k)
Non-recursive calculation of the partner node index is also possible.
- Batcher, Ken (1968), Sorting Networks and their Applications, AFIPS '68 (Spring), Atlantic City, New Jersey: Association for Computing Machinery, pp. 307–314, doi:10.1145/1468075.1468121, archived from the original on 2020-10-24
- D.E. Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Second Edition. Addison-Wesley, 1998. ISBN 0-201-89685-0. Section 5.3.4: Networks for Sorting, pp. 219–247.
- "Chapter 46. Improved GPU Sorting".
- "Sorting network from Batcher's Odd-Even merge: partner calculation". Renat Bekbolatov. Retrieved 7 May 2015.