Batcher odd–even mergesort

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search
Batcher odd–even mergesort
Visualization of the odd–even mergesort network with eight inputs
Visualization of the odd–even mergesort network with eight inputs
Class Sorting algorithm
Data structure Array
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!"[1]

It is popularized by the second GPU Gems book,[2] as an easy way of doing reasonably efficient sorts on graphics-processing hardware.

See also[edit]


  1. ^ 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.
  2. ^

External links[edit]