# 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.

Contents

## 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

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

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

Sorting first sequence in ascending order:

• First compare the elements
• Then compare the adjacent elements

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

Now, we will merge these two to get our final 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

Now compare and swap every second element of the sequence

We will now do the same for the adjacent elements

## 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])

```

## Complexity Analysis:

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

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

## 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!

Subscribe
Notify of 