Batcher's odd–even mergesort
is a generic construction devised by
Ken Batcher
Kenneth Edward Batcher (December 27, 1935 – August 22, 2019) was an American academic who was emeritus professor of Computer Science at Kent State University. He also worked as a computer architect at Goodyear Aerospace in Akron, Ohio for 28 y ...
for
sorting network
In computer science, comparator networks are abstract devices built up of a fixed number of "wires", carrying values, and comparator modules that connect pairs of wires, swapping the values on the wires if they are not in a desired order. Such ne ...
s 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!"
It is popularized by the second ''
GPU Gems
A graphics processing unit (GPU) is a specialized electronic circuit designed for digital image processing and to accelerate computer graphics, being present either as a discrete video card or embedded on motherboards, mobile phones, personal co ...
'' book, 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.
See also
*
Bitonic sorter
Bitonic mergesort is a parallel algorithm for sorting. It is also used as a construction method for building a sorting network. The algorithm was devised by Ken Batcher. The resulting sorting networks consist of O(n\log^2(n)) comparators and have ...
*
Pairwise sorting network
The pairwise sorting network is a sorting network
In computer science, comparator networks are abstract devices built up of a fixed number of "wires", carrying values, and comparator modules that connect pairs of wires, swapping the values on th ...
References
External links
Odd–even mergesortat hs-flensburg.de
Odd-even mergesort network generatorInteractive Batcher's Odd-Even merge-based sorting network generator.
{{DEFAULTSORT:Batcher odd-even mergesort
Sorting algorithms