Bitonic mergesort is a parallel sorting algorithm devised by Ken Batcher, also used as a construction method for building a sorting network. Its comparator network structure gives it a delay proportional to the square of the logarithm of the number of items being sorted, which has made it a popular choice for sorting large numbers of elements on hardware such as a GPU that contains many parallel execution units running in lockstep.
Facts
Time Complexity
Time Complexity (category)Linearithmic Time -- O(n log n) 1 Connections
Credited To
Source Bitonic sorter (Wikipedia)
In Field
Source Bitonic sorter (Wikipedia)
Invented By
Source Bitonic sorter (Wikipedia)
Uses Design Technique
Source Bitonic sorter (Wikipedia)
Sources
1. Bitonic Mergesort (Wikipedia)
Wikipedia infobox: time complexity linearithmicQuote, Wikipedia infobox: time complexity linearithmic
linearithmic
Wikidata: Bitonic Mergesort
Wikidata Q4918918, class allow-list match (w-wdresolver-0926)View the Source Bitonic sorter (Wikipedia)
Uses Design Technique: Recursion, Article body
With the sorter for k = 1 {\displaystyle k=1} , we can recursively create a sorter of higher order.
Invented By: Ken Batcher, Lead paragraph
The algorithm was devised by Ken Batcher.
Credited To: Ken Batcher, Lead paragraph
The algorithm was devised by Ken Batcher.
- In Field: Algorithms and Complexity Theory, Lead paragraph
In Group: Comparison Sorting Algorithms, Lead
Bitonic mergesort is a parallel algorithm for sorting.
View the SourceReader Challenges (0)
No disputes yet. Spotted an error or a better source? Open the first one.
Sign in to dispute this or suggest a correction.