Batcher odd–even mergesort
Appearance
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 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.
Example code
The following is an implementation of odd–even mergesort algorithm in Python. The input is a list x of length a power of 2. The output is a list sorted in ascending order.
def compare_and_swap(x, a, b):
if x[a] > x[b]:
x[a], x[b] = x[b], x[a]
def oddeven_merge(x, lo, hi, r):
step = r * 2
if step < hi - lo:
oddeven_merge(x, lo, hi, step)
oddeven_merge(x, lo + r, hi, step)
for i in range(lo + r, hi - r, step):
compare_and_swap(x, i, i + r)
else:
compare_and_swap(x, lo, lo + r)
def oddeven_merge_sort_range(x, lo, hi):
""" sort the part of x with indices between lo and hi.
Note: endpoints (lo and hi) are included.
"""
if (hi - lo 1:
# if there is more than one element, split the input
# down the middle and first sort the first and second
# half, followed by merging them.
mid = lo + ((hi - lo) / 2)
oddeven_merge_sort_range(x, lo, mid)
oddeven_merge_sort_range(x, mid + 1, hi)
oddeven_merge(x, lo, hi, 1)
def oddeven_merge_sort(x):
oddeven_merge_sort_range(x, 0, len(x)-1)
>>> data = [4, 3, 5, 6, 1, 7, 8]
>>> oddeven_merge_sort(data)
>>> data
[1, 2, 3, 4, 5, 6, 7, 8]
References
- ^ 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.
- ^ http://http.developer.nvidia.com/GPUGems2/gpugems2_chapter46.html
External links
- Odd–even mergesort at fh-flensburg.de