Odd-even mergesort

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

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

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

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.

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: