Batcher odd–even mergesort
Visualization of the odd–even mergesort network with eight inputs
|Worst-case performance||parallel time|
|Best-case performance||parallel time|
|Average performance||parallel time|
|Worst-case space complexity||non-parallel time|
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!"
- D.E. Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1998. ISBN 0-201-89685-0. Section 5.3.4: Networks for Sorting, pp. 219–247.