This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Bitonic sorter" – news · newspapers · books · scholar · JSTOR(October 2017) (Learn how and when to remove this message)
Bitonic sorter
Bitonic sort network with eight inputs.
Class
Sorting algorithm
Data structure
Array
Worst-case performance
parallel time
Best-case performance
parallel time
Average performance
parallel time
Worst-case space complexity
non-parallel time
Optimal
No
Bitonic mergesort is a parallel algorithm for sorting. It is also used as a construction method for building a sorting network. The algorithm was devised by Ken Batcher. The resulting sorting networks consist of comparators and have a delay of , where is the number of items to be sorted.[1] This makes it a popular choice for sorting large numbers of elements on an architecture which itself contains a large number of parallel execution units running in lockstep, such as a typical GPU.
A sorted sequence is a monotonically non-decreasing (or non-increasing) sequence. A bitonic sequence is a sequence with for some , or a circular shift of such a sequence.
Bitonic mergesort is a parallel algorithm for sorting. It is also used as a construction method for building a sorting network. The algorithm was devised...
In computer science, a sorting algorithm is an algorithm that puts elements of a list into an order. The most frequently used orders are numerical order...
comparison sorts, Pratt's version lends itself to sorting networks and has the same asymptotic gate complexity as Batcher's bitonicsorter. Gonnet and...
of Batcher's Bitonic Mergesort at O((log n)2) time on a butterfly sorting network is in practice actually faster than his O(log n) sorts on a PRAM, and...
switches. Since the 2000s, sorting nets (especially bitonic mergesort) are used by the GPGPU community for constructing sorting algorithms to run on graphics...
algorithms are based on modifications of the merge part of either the bitonicsorter or odd-even mergesort. In 2018, Saitoh M. et al. introduced MMS for...
parallel sorting algorithms available, for example optimal complexity O(log(n)) are those of the Three Hungarians and Richard Cole and Batcher's bitonic merge...
Multistage Interconnection Networks, 1992 Batcher odd–even mergesort Bitonicsorter "Archived copy" (PDF). Archived from the original (PDF) on 2019-05-17...
actual processors for such uses as sorting; cyclic shifting, as in a perfect shuffle network; and bitonicsorting. Interconnection network are used to...
use a form of merge sort to sort it; when two sequences are being merged to form a single longer sequence, the same bitonicsorting subroutine can be used...
add it to the end of the sorted list Smoothgamersort Other Bitonicsorter Pancake sorting Spaghetti sort Topological sort Unknown class Samplesort Longest...
trees bingo sort binomial heap binomial tree bin packing problem bin sort bintree bipartite graph bipartite matching bisector bitonicsort bit vector Bk...
sequences that instead use an exponential number of steps. The shortest bitonic tour (the minimum-perimeter monotone polygon through the given points)...
Global Information
