Bitonic (Merge) Sort | Explanation and Code Tutorial

Okay, so hey guys, my name is Quinston and today, we are going to explore the inner workings of the Bitonic Sort and the code that enables it. But before we jump into that. Thank you and let’s begin.

The Bitonic Sort is a parallel comparison-based sorting algorithm which does O(nlogn) comparisons. It is also called as the Bitonic Merge Sort. The Bitonic Sort is based on the concept of converting the given sequence into a Bitonic Sequence. Now, what in the world is a Bitonic Sequence?

A Bitonic Sequence is a sequence of numbers which is first strictly increasing then after a point strictly decreasing. So, the values of the elements of the sequence grow from the start and decrease towards the end. An example of this would be the sequence [ 6, 7, 8, 9, 5, 3, 2, 1 ]. In this example, the value of the elements increases from [ 6, 7, 8, 9 ] and then decreases from [ 5, 3, 2, 1 ]. It’s almost like looking at a gradient which goes up in value and comes down. The point at which the gradient reverses is called as the Bitonic Point. Also, the Bitonic Sort only works on sequences with a length that is in the order of the power of 2 like 4, 8, 16 etc. This might be a limitation but that is how it works.

A sequence which is sorted in the increasing order or an ascending sequence is also Bitonic as the decreasing part of the sequence is considered to be empty. Similarly, in a sequence that is sorted in the decreasing order or a descending sequence is also Bitonic as the increasing part is considered to be empty. Another important thing to remember is that the sequence when rotated, is still Bitonic. Rotation, in this case, is the process of either taking the first element of the sequence and appending it to the end of the sequence or taking the last element of the sequence and prepending it to the start sequence. Rotation preserves the Bitonic nature of the sequence.

Before stating the steps of the algorithm, there is one specific concept that you need to be aware of and that is, what is the smallest Bitonic Sequence possible? Let’s think about this. Going off the definition of the Bitonic Sequence, we would assume that the smallest Bitonic Sequence would be a sequence of 4 numbers, in which the first 2 elements are in an ascending order and the second two elements are in descending order. But, you would be making a grave mistake in this case, the reason for this is that, you don’t need both the ascending and descending parts to make a Bitonic Sequence. A pure ascending or a pure descending sequence is also a Bitonic Sequence. Now, let’s think deeper. What about two consecutive number? If you have 2 numbers back to back, let’s say they are 3 and 7. Simply put, 3 and 7 form an ascending sequence so they are Bitonic. If you swap their locations, which gives you 7 and 3. This is also Bitonic as it is a descending sequence. So, the realization is that any random two consecutive elements form a Bitonic Sequence.

Let’s take an example so that we have a better idea of how it works out. So, we shall consider the sequence…

[ 3, 7, 4, 8, 6, 2, 1, 5 ]

So, this was the most common sequence that is being used everywhere on the Internet to illustrate the Bitonic Sort, so I thought it would be a good idea to use the same.

Going off the principle that we realized previously, with the size of the sequence being 8, where are 4 Bitonic sequences that exist right now. They are namely, 3 and 7, 4 and 8, 6 and 2 and 1 and 5. The size of the current Bitonic Sequences is 2. We did not have to perform any operations to get to this stage. This is where we start executing the Algorithm from.

The first step is to figure out what is the size of the Bitonic Sequence that we need to form in the current sequence. We get this by doubling the size of the existing Bitonic Sequence. The size of the existing Bitonic Sequence is 2. Doubling this, we get 4. So, the size of the Bitonic Sequence that we need to form is 4.

The sequence contains 8 elements. From here, we consider 4 elements each and create 2 groups. We will now proceed to convert each of these groups into Bitonic Sequences. At this end of this cycle, we will have 2 Bitonic Sequences in our main Sequence. So, how do we from these sequences? We use 2 tools here namely, comparison distance and direction.

The comparison distance is the distance between the elements that you are going to compare and the direction is the order in which you want the values to be arranged in. If the elements are not arranged in the correct order in sync with the direction, those elements need to be swapped. The direction is marked with an arrow and the distance is marked with the length of the arrow. Let’s dive deeper into the example to see how this is implemented.

The first group contains the elements, [ 3, 7, 4, 8 ]. We have to convert this into a Bitonic Sequence. Now, we need to find the comparison distance. The distance is usually half the size of the existing Bitonic Sequence. In our case, the length of the Bitonic Sequence that we currently have is 2 and half of 2 is 1. So, we should compare elements which are at a distance of 1 from each other in the group. As this group has to be converted into a Bitonic Sequence, the first part of the sequence is supposed to be increasing and the next part of the sequence is supposed to be decreasing. To make this easier on our brains, we split the group into 2 equal parts. The first part contains the elements, 3 and 7 and the second part contains the elements, 4 and 8.

Now, we are supposed to draw arrows to signify which elements to compare and in which direction they need to be increasing and decreasing. The comparison distance is 1. We start at 3 and draw an arrow of length 1 from left to right. As this part of the group needs to be in the increasing order, the arrow points from left to right. We would think that the next arrow would need to be drawn from 7 but no. The previous arrow ends at 7 so 7 is already a part of a comparison. Multiple comparison cannot be done on the same elements simultaneously. The next arrow will be drawn from 4 with a distance of 1. This part of the group is supposed to be in the descending order hence, the direction of the arrow will be from right to left.

Similarly, in the second group, [ 6, 2, 1, 5 ]. We replicate the same process. Drawing arrows from 6 with a distance of 1 pointing left to right and drawing arrows from 1 with a distance of 1 pointing right to left. Now, it’s time to either swap or maintain the position of the elements.

3 and 7 are in the correct order of increase in value as they are in sync with the direction of the arrow, hence their positions are maintained. 4 and 8 are not in the correct order so they need to be swapped. 6 and 2 are not in the correct direction so they need to be swapped. 1 and 5 are also not in the correct direction so they need to be swapped. These operations give us the sequence, [ 3, 7, 8, 4, 2, 6, 5, 1 ]. This is the end of the first stage.

The Bitonic Sort is composed of stages and passes. Passes are a subset of stages. A stage change is when you move from forming a smaller Bitonic Sequence to a larger Bitonic Sequence. A pass change is when you start comparing elements, in the same group, of a distance half of the previous distance recursively. Let’s go to the next stage to delve deeper into understanding this.

Stage 2 involves progressing upwards to form a larger Bitonic Sequence. The Bitonic Sequence that we need to form when transitioning to a new stage is twice the size of the existing Bitonic Sequence. The existing Bitonic Sequence is of length 4, so the next Bitonic Sequence should be of size 8. The whole sequence that we currently have has 8 elements inside it. So, we don’t need to make any groups and have to convert the entire sequence into a Bitonic Sequence. The next step in the algorithm is to calculate the comparison distance. The comparison distance, again, is half the length of the existing Bitonic Sequence. The length of the existing Bitonic Sequence, again, is 4 so the comparison distance is 2, as 2 is half of 4. Let’s draw our arrows. As the Bitonic Sequence we need to form is of length 8, the first 4 elements are supposed to be in the increasing order and the next 4 elements are supposed to be in the decreasing order.

So, we start by drawing an arrow from the first element, which is 3. The arrow is of length 2 so it ends at 8. This portion of the sequence is supposed to be in an increasing order so the arrow point from left to right. Next, we draw an arrow from the next element, which is 7. The arrow ends at 4 and is of length 2. Again, arrow points from left to right. We would assume that the next arrow will be from 8, but no. You cannot draw an arrow from 8 as the element is already a part of an operation that is not yet finished. Also, another reason is that if you draw an arrow from 8, with the length of 2, it will enter into the the decreasing portion which is not allowed. Cross-pollination or more specifically, cross comparison and swapping is not allowed. These are two different portions and they should be treated like that. Similarly, we cannot draw an arrow from 4 either adhering to the rules we just talked about.

So, moving on to the next portion of the sequence, we draw an arrow from 2 to 5. This arrow is pointing from right to left as this portion needs to be arranged in the descending order. Similarly, an arrow gets drawn from 1 to 6 which points from right to left. Now, execute.

7 gets swapped with 4 and 2 gets swapped with 5 because they are in the wrong directions. In the previous stage, we stopped here and moved on to the next stage. But, we cannot do that over here as the sequence that we just got is not Bitonic. We need to finish all of the passes in this stage to achieve a fully Bitonic Sequence. So, how do we transition to a new pass in this stage? Divide the current comparison distance by 2 and repeat the process. Let’s do that.

The current comparison distance is 2, so if we half it, we get 1. So, let’s draw arrows of length 1 in our existing increasing and decreasing order portions of the group. An arrow gets from from 3 of length 1, from the left to right. We cannot draw an arrow from 4 as it part of an operation that is not yet finished. We draw an arrow from 8 of length 1, left to right. Similarly, an arrow pointing right to left from 5 of length 1 and an arrow pointing from right to left 2 of length 1. Let’s execute.

8 gets swapped with 7 and 5 gets swapped with 6 to rearrange in the correct order of values. We would want to move to the next pass in this stage but when we half the comparison distance, we get a length of 0.5 which is floored to 0. No elements exist at a distance of 0.5 or 0 from each other. Hence, that is the end of this stage and we end up with a sequence of [ 3, 4, 7, 8, 6, 5, 2, 1 ]. When you think about it, the reason we did not have another pass in the first stage was because the initial comparison distance was 1 so there was no reason to have another pass.

Moving on to the next stage, we need to find the size of the Bitonic Sequence that we need to form. The size of the existing Bitonic Sequence is 8 so, the length of the next Bitonic Sequence is going to be double of 8, which is 16. But you might be like… wait. The size of the whole sequence is 8. How can we make a Bitonic Sequence of size 16. The answer is, you don’t. You just pretend that you are making a Bitonic Sequence of size 16 and in the process, you end up sorting your current size 8 Bitonic Sequence. How insane is that? Just think about that for a while. It’s crazy.

Let’s jump into the first pass of this stage. Our initial comparison distance is half the size of the current Bitonic Sequence. The current Bitonic Sequence is of size 8, so the comparison distance is of size 4. We are forming a Bitonic Sequence of size 16, hence the first 8 elements are going to be in the ascending order and the next 8 elements, well, they don’t exist. But if they did, they would be in the descending order. Let’s draw our arrows.

Arrows get in the left to right direction from 3 to 6, 4 to 5, 7 to 2 and 8 to 1. 7 gets swapped with 2 and 8 gets swapped with 1 to maintain the correct directions. Moving to the next pass, the comparison distance becomes half of 4, which is 2. An arrow gets drawn from 3 to 2, 4 to 1, 6 to 7 and 5 to 8. All of the arrows are from left to right. 3 gets swapped with 2 and 4 gets swapped with 1.

For the next pass, the comparison distance gets halved so it becomes 1 from 2. Arrows pointing left to right get drawn from 2 to 1, 3 to 4, 6 to 5 and 7 to 8. 2 gets swapped with 1, 3 gets swapped with 4 and 6 gets swapped with 5. We cannot move to the next pass as halving the distance here would give us a value less than 1. This the end of the current stage. The sequence we end up with is [ 1, 2, 3, 4, 5, 6, 7, 8 ].

The sequence is sorted as you can clearly see. That is how the Bitonic Sort actually works.

You can find the fully-commented code on my Github.

Learn ‘How To Build A SaaS Side-Hustle That Actually Makes Money’ — For Programmers and Hackers That Can Build Software Independently.

Use Coupon Code ‘launch30’ for 30% off.

I also make fun engaging videos on Data Structures and Algorithms on YouTube. I am sure they will provide a lot of value to you on your journey of becoming an elite Programmer. Find the link to the channel here.