Bitonic Sort is a sorting algorithm based on comparisons. It exploits binary sequences, so it can be applied only on data structures with number of elements equal to a power of 2.
The algorithm is made up of two parts. Initially, the data structure gets converted to a binary sequence, creating groups of ascending and descending elements linked together. Next, the groups get merged with an algorithm similar to Merge Sort until the data structure is sorted.
It can be implemented in numerous variants, iteratively or recursively, with different visualizations. This visualization shows an iterative version.
Average Complexity | O(log^{2} n) |
---|---|
Best Case | O(log^{2} n) |
Worst Case | O(log^{2} n) |
Space Complexity | O(n × log^{2} n) |