Updated April 6, 2023
Introduction to Bitonic Sort
Bitonic sort is parallel sorting algorithm that performs comparisons. Number of comparisons done by Bitonic sort are more compared to other popular sorting algorithms. This sort is better for parallel implementation as user always compares the elements in a predefined sequence and this sequence of comparison does not actually depend upon data. And hence this bitonic sort is basically suitable for hardware implementations. Before understanding what Bitonic sort is, we need to understand what Bitonic sequence means and how a sequence is made to bitonic. Let us dig deeper and understand Bitonic sorting with a few examples.
Bitonic Sequence
Bitonic sequence is an array such as arr[0, 1, …..(n-1)], if there is index value i in the range of 0 to (n-1) for which any value of arr[i] is greatest. This is represented as below,
arr[0] <= arr[1], arr[1] <= arr[2],…… & arr[i] >= arr[i+1], arr[i+1] >= arr[i+2]…… >= arr[n-1]
Sequence is called Bitonic if its in first increasing and then decreasing. The sequence that is sorted in ascending order is considered to be Bitonic with descending sequence as empty. Similarly, descending order is considered to be Bitonic with ascending sequence as empty.
Rotation of a Bitonic sequence is also known as Bitonic. Specifically, Bitonic sort can also be modelled as one of the type of sorting network.
Bitonic sort Algorithm was created by Ken Batcher in the year 1968, that had two parts.
- Unsorted sequence built into Bitonic sequence.
- Series split multiple times to smaller sequences until and unless input provided is in sorted order.
Example of Bitonic Sequence
Bitonic sequence can be rotated in such a way that it can retains its bitonic sequence. A sequence in which elements are in increasing and decreasing order is a bitonic sequence.
Let us consider an example for creating a bitonic sequence,
Array[] = {2, 3, 4, 7, 5, 6, 8, 9}
- Step 1: To create a bitonic sequence, we need to first create 2 sub sequences, one in ascending and the other in descending.
- Step 2: Create pairs of elements.
Array[] = {(2, 3), (4, 7), (5, 6), (8,9)}
Array[] ={(2, 3), (7, 4), (5, 6), (9, 8)}
- Step 3: Then create pairs of these pairs in 4 elements in bitonic sequence and compare these elements which are at distance 2 i.e., i and i+2
Array[] = {(2, 3, 7, 4), (5, 6, 9, 8)}
- Step 4: Ascending bitonic sequence in the first set,
(2, 3, 7, 4), compare two distant elements and checking adjacent elements.
(2, 3, 4, 7), this is the ascending bitonic sequence.
- Step 5: Descending bitonic sequence in the second set,
(5, 6, 9, 8), compare two distant elements and checking adjacent elements.
(9, 8, 6, 5)
- Step 6: Bitonic sequence is created with size 8,
2, 3, 4, 7, 9, 8, 6, 5
Bitonic Sorting Algorithm
Bitonic sorting involves the following steps,
- Step 1: First, we need to form a Bitonic sequence for the given random sequence array. As we have already formed a Bitonic sequence in the above example, we shall consider that for Bitonic sorting.
- Step 2: We need to compare the first element in the first half with the first element in the second half, moving to the second element in the first half with the second element in the second half and this continues till the last element of the first half is compared with the last element of the second half. Swap the elements if element in second half is comparatively smaller than that in the first half.
- Step 3: Hence, all the first half elements will be now smaller than the second half elements. This compare and swap results with two sequences of n/2 length. Repeat step 2 in recursive manner to every sequence until there is a single sorted sequence of length n.
Let us see in practical How Bitonic sort is done, following the above algorithm,
Bitonic sequence: 2, 3, 4, 7, 9, 8, 6, 5
So in this way, Bitonic sorting is done.
Random sequence was applied a Bitonic sequence above and then Bitonic sequence was taken as an input for Bitonic sort.
The first element of first-half ———– first element of the second half
2 < 9, hence no change
Second element of first half ———- second element of second half
3 < 8, hence no change
The third element of the first-half ———— third element of the second half
4 < 6, hence no change
Last element of first half ———– last element of second half
7 > 5, hence 5 and 7 are swapped.
Now, as the first half has all elements less than that of second half and also has been sorted in ascending order properly.
Will only consider second half of the sequence for sorting now,
First element of first-half ———- first element of second half
9 > 6, hence both are swapped.
Second element of first half ——— second element of second half
8 > 7, hence both are swapped.
Now as you have seen above only one set of elements is left for comparison,
9> 8, hence swapped.
So the final Bitonic sorted output is,
2, 3, 4, 5, 6, 7, 8, 9
Time Complexity of Bitonic Sorting
When Bitonic sort runs in parallel, bitonic sorting gets completed in O(n log2n) comparisons for space complexity that too the worst case. Parallel versions of sort can lead to speed depending on implementations.
For Time complexity, it is O(n log2n) for all cases.
With this, we shall conclude the topic ‘Bitonic sort’. We have seen what doe Bitonic sort mean and how it is dependent on Bitonic sequence. We have also seen an example for implementing Bitonic sort, for which Bitonic sequence was applied first and then the output of Bitonic sequence served as input for Bitonic sort. We have also seen Algorithms for implementing Bitonic sorting as well as for Bitonic sequence. Time complexity for Bitonic sort is O(n log2 n) is all cases.
Recommended Articles
This is a guide to Bitonic Sort. Here we also discuss the introduction and example of bitonic sequence along with time complexity of bitonic sorting. You may also have a look at the following articles to learn more –
