Batcher odd–even mergesort

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]

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

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

Pseudocode

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

• Bitonic sorter
• Pairwise sorting network