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)^{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!"^{[1]}
It is popularized by the second GPU Gems book,^{[2]} as an easy way of doing reasonably efficient sorts on graphicsprocessing 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. AddisonWesley, 1998. ISBN 0201896850. 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 fhflensburg.de
Sorting algorithms Theory Exchange sorts Selection sorts  Selection sort
 Heapsort
 Smoothsort
 Cartesian tree sort
 Tournament sort
 Cycle sort
Insertion sorts Merge sorts Distribution sorts Concurrent sorts  Bitonic sorter
 Batcher odd–even mergesort
 Pairwise sorting network
Hybrid sorts  Timsort
 Introsort
 Spreadsort
 UnShuffle sort
 JSort
Quantum sorts Other Categories: Algorithm stubs
 Sorting algorithms
 Ken Batcher
Wikimedia Foundation. 2010.
Look at other dictionaries:
Batcher oddeven mergesort — 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). Unlike a mergesort, this algorithm is not data dependent.It is popularised by the first GPU Gems… … Wikipedia
Odd–even sort — Example of odd even transposition sort sorting a list of random numbers. Class Sorting algorithm Data structure Array Worst case performance … Wikipedia
Merge sort — Example of merge sort sorting a list of random dots. Class Sorting algorithm Data structure Array Worst case performance O(n log n) … Wikipedia
Sorting algorithm — In computer science, a sorting algorithm is an algorithm that puts elements of a list in a certain order. The most used orders are numerical order and lexicographical order. Efficient sorting is important for optimizing the use of other… … Wikipedia
Counting sort — In computer science, counting sort is an algorithm for sorting a collection of objects according to keys that are small integers; that is, it is an integer sorting algorithm. It operates by counting the number of objects that have each distinct… … Wikipedia
Comb sort — Class Sorting algorithm Data structure Array Worst case performance O(n log n)[1] … Wikipedia
Pigeonhole sort — Class Sorting algorithm Data structure Array Worst case performance O(N + n), where N is the range of key values and n is the input size Worst case space complexity O(N * n) … Wikipedia
Bogosort — Class Sorting algorithm Data structure Array Worst case performance [1] Best case performance Ω … Wikipedia
Cocktail sort — Class Sorting algorithm Data structure Array Worst case performance О(n²) Best case performance O(n) … Wikipedia
Topological sorting — Dependency resolution redirects here. For other uses, see Dependency (disambiguation). In computer science, a topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that, for every edge uv, u comes… … Wikipedia