Jump to content

Batcher odd–even mergesort

From Wikipedia, the free encyclopedia
(Redirected from Odd-even mergesort)
Batcher odd–even mergesort
Visualization of the odd–even mergesort network with eight inputs
Visualization of the odd–even mergesort network with eight inputs
ClassSorting algorithm
Data structureArray
Worst-case performance parallel time
Best-case performance parallel time
Average performance parallel time
Worst-case space complexity non-parallel time
OptimalNo

Batcher's odd–even mergesort[1] 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!"[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]

References

[edit]
  1. ^ Batcher, Ken (1968), "Sorting Networks and their Applications", Proceedings of the April 30--May 2, 1968, spring joint computer conference on - AFIPS '68 (Spring), Atlantic City, New Jersey: Association for Computing Machinery, pp. 307–314, doi:10.1145/1468075.1468121, S2CID 207171031, archived from the original on 2020-10-24
  2. ^ D.E. Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Second Edition. Addison-Wesley, 1998. ISBN 0-201-89685-0. Section 5.3.4: Networks for Sorting, pp. 219–247.
  3. ^ "Chapter 46. Improved GPU Sorting".
  4. ^ "Sorting network from Batcher's Odd-Even merge: partner calculation". Renat Bekbolatov. Retrieved 7 May 2015.
[edit]