Batcher Odd-Even Mergesort

Batcher's odd-even mergesort is a generic construction devised by Ken Batcher for sorting networks of size O(n(log n) squared) and depth O((log n) squared), where n is the number of items to be sorted. Although it is not asymptotically optimal, Donald Knuth concluded in 1998, comparing it with the theoretically superior AKS sorting network, that Batcher's method is much better unless n exceeds the total memory capacity of every computer on earth, and the method has been popularized as an easy way of performing reasonably efficient sorts on graphics-processing hardware.