Batcher odd–even mergesort

Visualization of the odd–even mergesort network with eight inputs

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 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

  1. ^ 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.
  2. ^ http://http.developer.nvidia.com/GPUGems2/gpugems2_chapter46.html

External links


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • 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). 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


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.