Bitonic Sort or bitonic merge sort algorithm is a parallel algorithm for sorting
. It is also used as construction method for building a sorting network.
The algorithm was devised by Ken Batcher. The resulting sorting networks
consist of O(n log^2 (n)) comparators and have a delay of O(log^2 (n)),
where n is the number of items to be sorted.
Time Complexity: O(n log^2 (n)) - Butonic sort involves constructing
bitonic sequences and repeatedly splitting them and rearranging them
to form new bitonic sequences. It involves log n stages, and at each
stage, there are O(n) comparisons.
Space Complexity: O(1) - Bitonic sort is in-place sorting algorithm,
meaning it doesn't require extra space or auxiliary arrays for sorting the
input.
Bitonic sort is not commonly used for general-purpose sorting due to its
non-competitive time complexity compared to faster, simpler algorithms like
QuickSort or MergeSort. However, it has its uses in parallel processing
systems because of its ability to sort in a parallel manner.
Type Parameters
TElement extends string | number
Parameters
arr: TElement[]
unsorted array should be size of power of 2 - (1, 2, 4, 8, 16, ...)
Bitonic Sort or bitonic merge sort algorithm is a parallel algorithm for sorting . It is also used as construction method for building a sorting network. The algorithm was devised by Ken Batcher. The resulting sorting networks consist of O(n log^2 (n)) comparators and have a delay of O(log^2 (n)), where n is the number of items to be sorted.
Time Complexity: O(n log^2 (n)) - Butonic sort involves constructing bitonic sequences and repeatedly splitting them and rearranging them to form new bitonic sequences. It involves log n stages, and at each stage, there are O(n) comparisons.
Space Complexity: O(1) - Bitonic sort is in-place sorting algorithm, meaning it doesn't require extra space or auxiliary arrays for sorting the input.
Bitonic sort is not commonly used for general-purpose sorting due to its non-competitive time complexity compared to faster, simpler algorithms like QuickSort or MergeSort. However, it has its uses in parallel processing systems because of its ability to sort in a parallel manner.