Batcher odd–even mergesort

Batcher odd–even mergesort

Visualization of the odd–even mergesort network with eight inputs
Class	Sorting algorithm
Data structure	Array
Worst-case performance	${\displaystyle O(\log ^{2}(n))}$ parallel time
Best-case performance	${\displaystyle O(\log ^{2}(n))}$ parallel time
Average performance	${\displaystyle O(\log ^{2}(n))}$ parallel time
Worst-case space complexity	${\displaystyle O(n\log ^{2}(n))}$ non-parallel time
Optimal	No

Batcher's odd–even mergesort^[1] is a generic construction devised by Ken Batcher for sorting networks of size O(n (log n)²) and depth O((log n)²), 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!"^[2]

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

Pseudocode[edit]

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.^[4]

See also[edit]

• Bitonic sorter
• Pairwise sorting network

References[edit]

External links[edit]

• Odd–even mergesort at hs-flensburg.de
• Odd-even mergesort network generator Interactive Batcher's Odd-Even merge-based sorting network generator.