The **bitonic sort** is a **comparison based sorting technique** in which the array is sorted by using a different type of sequence called the **bitonic sequence**. The **bitonic sequence of an array is the sequence of elements **where the elements are increasing up to a certain element and then the value will be decreasing till end. For example, an array with n elements will be called in a **bitonic sequence** if:

**PROCEDURE WITH EXAMPLE:**

Suppose there is an array of **8 elements** as follows:

The array should be sorted in **ascending order**.

**Step 1**:

In the **first step**, **two consecutive elements are compared** and a **bitonic sequence**** is formed for **the **first 4 elements**, then **the next four elements**, and so on as the following:

The **first two elements will be compared**; as they are already in **increasing order** so there will be **no change**.

Now, the **second two elements will be checked**, they **should be sorted in ****decreasing order**. As here they will not be in **decreasing order** so they will be **swapped**.

For the **next pair of elements,** it should be **again in ****increasing order**. As they are **not incorrect **orders they will be **swapped**. Similarly, for the **last pair, it should be in descending order**. As they are already in **descending order** so there will be **no swapping**. After this step, we get two 4 elements bitonic sequence.

**Step 2**:

Now, in the **2nd step**** the elements** will be **compared at ****gap 2** to form **8 elements ****bitonic sequence** as follows:

Now, **firstly the ****4**** and ****8**** will be compared**, as they are **in ****ascending order** so there will **not be swapped****.**

**Next ****7**** and ****-9**** will be compared**, as they are **not in ****ascending order**, they will **be swapped****.**

**Next ****5**** and ****3**** will be compared**, they are already in **descending order****,** there will **not be swapping****.**

**Then** **12**** and ****-2**** will be compared next**, they are also in **descending order** so there will also **not be swapping****.**

**Step 3:**

In this step, again the **adjacent pairs of elements will be compared**. But **unlike step 1**, **the first two pair will be arranged in ****ascending order**; the **next two pairs will be arranged in ****descending** **order**.

Now, **4 and -9 will be compared** and will be arranged in **ascending order**, so, it will be** swapped.**

**8 and 7 will be compared** and again will be arranged in **ascending order**, so, it will be **swapped.**

For the next half, **5 and 12 will be compared** and will be **arranged in descending order**. So, it will be **swapped.**

Similarly, **3 and -2 will be compared** but as they **are ****already in descending order**, so there will be **no change**.

After this sequence, we get the full array arranged in a **bitonic sequence**.

**Step 4:**

In this step, the elements at **gap 4** will be compared and **will be arranged in ****ascending order** as follows:

The **first element(-9)** will **be compared with the ****5th element (12)**, as they are **already in sorted** order, they will **not be swapped**.

Next **4 and 5 will be compared**, so, **no swapping required**.

Now **7 will be compared with 3**, they will **be swapped**.

Lastly, **8 and -2 will be compared** and will be **swapped**.

**Step 5:**

In this step again the elements at **gap 2** will be compared and to arrange in **ascending order** as follows:

First **-9 is compared with 3**, they are **already in ****ascending order** so there will be **no swapping**.

Next **4 and -2 will be compared** and they **will be swapped** to arrange in the correct order.

Next, **12 and 7 will be compared** and will be swapped and arranged in ascending order.

Similarly, **5 and 8 will be compared** but there will be **no change** as they are already in the correct sequence.

**Step 6:**

This is the last step of this sorting in which again the **adjacent elements will be compared** and arranged in **ascending order**.

First **-9 and -2 will be compared**, as they are in **sorted order**, **no swapping required**.

**Next 3 and 4 will be compared**, they are also in **sorted order**, **no swapping required**.

Then **7 and 5 will be compared**, they are **not in ascending** order so they will **be swapped**.

Lastly, **12 and 8 will be compared** and **swapped**. After this, we will get the final array as:

**Sorted Array:**

```
INPUT: An unsorted array [98,34,12,.........,n]
OUTPUT: A sorted array[12,34,...............,n]
PROCESS:
Step 1: [Take the inputs from the user]
Read n
For i=0 to n repeat
Read arr[i]
Step 2: [function to compare]
if dir=a[i]>a[j] then
Swap a[i] and a[j]
[End of ‘if’]
Step 3:[function to merge the array]
if count>1 then
Set k <- count/2
for i=l to l+k
Call the ‘compare(a, i, i+k, dir)’ function
Call the ‘merge(a, l, k, dir)’ function
Call the ‘merge(a, l+k, k, dir)’
[End of ‘if’]
Step 4: [bitonic function]
if count>1 then
Set k <- count/2
Call the function ‘bitonic(a, l, k, 1)’
Call the function ‘bitonic(a, l+k, k, 0)’
Call the function ‘merge(a,l, count, dir)’
[End of ‘if’]
Step 5: call the function ‘bitonic(a,0,n,up)’
Step 6:[Display the sorted array]
For i=0 to n repeat
Print a[i]
```

__CHARACTERISTICS:__

**1.** It is a comparison-based sorting technique.

**2.** The elements are sorted depending on a special sequence called the bitonic sequence.

**3.** It can be implemented in parallel programming.

__TIME COMPLEXITY:__

If there is **n number of elements** in an array, then to form a **bitonic sequence of ****n elements**** from two sorted ****sequences of n/2**, the number of **comparisons required** is: **log(n)**.

The **total number of sorting** required to sort the elements are:

__SPACE COMPLEXITY:__

For **non-parallel implementation** of the Bitonic Sort,

__ADVANTAGES:__

**1.** It can be easily implemented in parallel computing.

**2.** More efficient than the quick sort algorithm.

__DISADVANTAGES:__

**1.** The number of comparisons in bitonic sort is more than many other popular sorting algorithms.

__APPLICATIONS:__

**1.** The **bitonic sort** is generally used to sort the elements of the array in **parallel computing**. The algorithm can be implemented in parallel computation efficiently.

Related

- Comb Sort
- Gnome sort
- Shell Sort
- Tree Sort
- List Sort
- Minmax Sort
- Intro Sort
- Cocktail Sort
- Counting Sort
- Bucket Sort
- Radix Sort for positive integer
- Heap Sort Iterative
- Heap Sort using recursion
- 3 way Merge Sort
- Merge Sort Iterative
- Merge Sort using recursion
- Quicksort Iterative
- Quick Sort using recursion
- Insertion Sort
- Selection Sort
- Bubble Sort
- Tim Sort

Contributed by