Batcher odd-even mergesort
- 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" book, as an easy way of doing reasonably efficient sorts on graphics-processing hardware.
External links
* [http://www.iti.fh-flensburg.de/lang/algorithmen/sortieren/networks/oemen.htm Description: Odd-even mergesort]
Wikimedia Foundation.
2010.
Look at other dictionaries:
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 … 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
