Bitonic sort: Algorithm and Implementation in Python

Hello coders!! In this article, we will be learning about the python bitonic sort algorithm and its implementation in Python. Sorting is the way of arranging the elements in a specific order, i.e., either in ascending or descending order. There are various sorting algorithms available, all having their own pros and cons. The bitonic sort is a parallel sorting algorithm that sorts the elements through comparisons.

What is the Bitonic sort?

It is a sorting algorithm that runs parallel. In this algorithm, there are O(n2 log n) comparisons. Although the number of comparisons is more, it’s more suitable for parallel implementation because the elements are compared in a predefined sequence (the bitonic sequence) that doesn’t depend on data. Therefore it is optimal for implementation in hardware and parallel processor array.

What is the Bitonic sequence?

In this sequence, after some particular index, the elements start decreasing whereas before that index the elements come in increasing order.

x0 <= x1 …..<= xi  and  xi >= xi+1….. >= xn-1
  • A sequence in increasing order is said to be Bitonic with the decreasing part as empty. Similarly, the decreasing sequence is said to be Bitonic, with the increasing part as empty.
  • A Bitonic Sequence, when rotated, is also bitonic.

How to convert Random sequence to Bitonic sequence?

Let us first consider the following elements of an array

Random Sequence Elements
Random Sequence Elements

First, we will make pairs of elements. We will then create its bitonic sequence such that one is in ascending order and the other is in descending order and so on.

Taking pairs of two and sorting in first ascending then descending order
Taking pairs of two and sorting in first ascending then descending order

Now, we will make pairs of each pair such that every sequence has four elements.

Groups of four elements
Groups of four elements

Sorting first sequence in ascending order:

  • First compare the elements
  • Then compare the adjacent elements
bitonic sort python
Sorting the first half in ascending order

Similarly, we will sort the second sequence in descending order:

Sorting the second half in descending order
Sorting the second half in descending order

Now, we will merge these two to get our final bitonic sequence

Bitonic Sequence
Bitonic Sequence

Bitonic Sort Algorithm:

  • At first, we will create a bitonic sequence.
  • Next we need to compare and sort the corresponding elements of both the halves of the sequence
  • Now, we will compare and swap every second element of the sequence
  • At last, we will compare and swap adjacent elements of the sequence

Illustration of Bitonic Sort Algorithm:

Let us consider the above created bitonic sequence.

At first we will compare and sort the corresponding elements of both the halves of the sequence

bitonic sort python

Now compare and swap every second element of the sequence

sorting using bitonic sort

We will now do the same for the adjacent elements

bitonic sort python

Source Code in Python:

def compare_swap(a, i, j, d):
    if (d == 1 and a[i] > a[j]) or (d == 0 and a[i] < a[j]):
        a[i], a[j] = a[j], a[i]
 

def merge(a, l, cnt, d):
    if cnt > 1:
        k = int(cnt / 2)
        for i in range(l, l + k):
            compare_swap(a, i, i + k, d)
        merge(a, l, k, d)
        merge(a, l + k, k, d)

def bitonic_sort(a, l, cnt, d):
    if cnt > 1:
        k = int(cnt / 2)
        bitonic_sort(a, l, k, 1)
        bitonic_sort(a, l + k, k, 0)
        merge(a, l, cnt, d)
 

def sort(a, N, u):
    bitonic_sort(a, 0, N, u)
 
a = [3, 4, 1, 9, 2, 7, 5, 6]
n=len(a)
   
u = 1
 
sort(a, n, u)
print("\nSorted array is")
for i in range(n):
    print("%d" % a[i])

Output:

Output of bitonic sort

Complexity Analysis:

  • Time complexity: O(log 2 n)
  • Space complexity: O(n log 2 n)

Advantages:

  • Memory is well handled by the process
  • Best suited for parallel processor array

Bitonic Sort vs Merge Sort:

Bitonic SortMerge Sort
Comparison based parallel algorithmDivide and conquer algorithm
O(n Log 2n) comparisons are done O(nLogn) comparisons are done
smaller numbers of each pair are moved to the left and larger numbers to right.input array is divided into two halves and then the function calls itself for the two halves, and ultimately the sorted halves are merged
Time complexity: O(log 2 n)Time complexity: O(nLogn) 

Must Read

Conclusion:

All sorting algorithms have their own pros and cons. Even though the number of comparisons in bitonic sort python is more, it is best suited for parallel arrays.

However, if you have any doubts or questions, do let me know in the comment section below. I will try to help you as soon as possible.

Happy Pythoning!

5 1 vote
Article Rating
Subscribe
Notify of
guest
0 Comments
Inline Feedbacks
View all comments