Batcher odd–even mergesort


Batcher's odd–even mergesort is a generic construction devised by Ken Batcher for sorting networks of size O and depth O, 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 book, 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 oddeven_merge:
step = r * 2
if step <= hi - lo:
yield from oddeven_merge
yield from oddeven_merge
yield from
else:
yield
def oddeven_merge_sort_range:
""" sort the part of x with indices between lo and hi.
Note: endpoints are included.
"""
if >= 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 +
yield from oddeven_merge_sort_range
yield from oddeven_merge_sort_range
yield from oddeven_merge
def oddeven_merge_sort:
""" "length" is the length of the list to be sorted.
Returns a list of pairs of indices starting with 0 """
yield from oddeven_merge_sort_range
def compare_and_swap -> None:
if x > x:
x, x = x, x


>>> data =
>>> pairs_to_compare = list
>>> pairs_to_compare
>>> for i in pairs_to_compare: compare_and_swap
>>> data

More concise and non-recursive calculation of partner node is possible. Here is a Scala implementation to get the partner of an index at each step:

def partner: Int =