what is Bitonic Sort?

Bitonic Sort

Bitonic sort is a parallel sorting algorithm which performs O(n2 log n) comparisons. Although, the number of comparisons are more than that in any other popular sorting algorithm, It performs better for the parallel implementation because elements are compared in predefined sequence which must not be depended upon the data being sorted. The predefined sequence is called Bitonic sequence.

What is Bitonic Sequence ?

In order to understand Bitonic sort, we must understand Bitonic sequence. Bitonic sequence is the one in which, the elements first comes in increasing order then start decreasing after some particular index. An array A[0... i ... n-1] is called Bitonic if there exist an index i such that,

1. A[0] < A[1] < A[2] .... A[i-1] < A[i] > A[i+1] > A[i+2] > A[i+3] > ... >A[n-1]  

where, 0 <= i <= n-1. A rotation of Bitonic sort is also Bitonic.

How to convert Random sequence to Bitonic sequence ?

Consider a sequence A[ 0 ... n-1] of n elements. First start constructing Bitonic sequence by using 4 elements of the sequence. Sort the first 2 elements in ascending order and the last 2 elements in descending order, concatenate this pair to form a Bitonic sequence of 4 elements. Repeat this process for the remaining pairs of element until we find a Bitonic sequence.

After this step, we get the Bitonic sequence for the given sequence as 2, 10, 20, 30, 5, 5, 4, 3.

Bitonic Sorting :

Bitonic sorting mainly involves the following basic steps.

1. Form a Bitonic sequence from the given random sequence which we have formed in the above step. We can consider it as the first step in our procedure. After this step, we get a sequence whose first half is sorted in ascending order while second step is sorted in descending order.
2. Compare first element of first half with the first element of the second half, then second element of the first half with the second element of the second half and so on. Swap the elements if any element in the second half is found to be smaller.
3. After the above step, we got all the elements in the first half smaller than all the elements in the second half. The compare and swap results into the two sequences of n/2 length each. Repeat the process performed in the second step recursively onto every sequence until we get single sorted sequence of length n.

The whole procedure involved in Bitonic sort is described in the following image.

Complexity

Complexity	Best Case	Average Case	Worst Case
Time Complexity	O(log 2 n)	O(log 2 n)	O(log 2 n)
Space Complexity			O(n log 2 n)

C Program

1. //this program works when size of input is power of 2.   
2. #include<stdio.h>  
3. void exchange(int arr[], int i, int j, int d)  
4. {  
5.     int temp;  
6.     if (d==(arr[i]>arr[j]))  
7.     {  
8.             temp = arr[i];  
9.         arr[i] = arr[j];  
10.         arr[j] = temp;  
11.     }  
12. }  
13. void merge(int arr[], int l, int c, int d)  
14. {  
15.     int k,i;  
16.     if (c>1)  
17.     {  
18.         k = c/2;  
19.         for (i=l; i<l+k; i++)  
20.             exchange(arr, i, i+k, d);  
21.         merge(arr, l, k, d);  
22.         merge(arr, l+k, k, d);  
23.     }  
24. }  
25. void bitonicSort(int arr[],int l, int c, int d)  
26. {  
27.     int k;  
28.     if (c>1)  
29.     {  
30.         k = c/2;  
31.         bitonicSort(arr, l, k, 1);  
32.         bitonicSort(arr, l+k, k, 0);  
33.         merge(arr,l, c, d);  
34.     }  
35. }  
36.    
37. void sort(int arr[], int n, int order)  
38. {  
39.     bitonicSort(arr,0, n, order);  
40. }  
41. int main()  
42. {  
43.     int arr[]= {1, 10, 2, 3, 1, 23, 45, 21};  
44.     int n = sizeof(arr)/sizeof(arr[0]);  
45.     int i;  
46.     int order = 1;     
47.     sort(arr, n, order);  
48.    
49.     printf("Sorted array: \n");  
50.     for (i=0; i<n; i++)  
51.         printf("%d ", arr[i]);  
52. }  

Output:

Sorted array: 
1 1 2 3 10 21 23 45

Java

1. //this program works when size of input is power of 2.   
2. public class BitonicSort  
3. {  
4. static void exchange(int arr[], int i, int j, boolean d)  
5. {  
6.     int temp;  
7.     if (d==(arr[i]>arr[j]))  
8.     {  
9.             temp = arr[i];  
10.         arr[i] = arr[j];  
11.         arr[j] = temp;  
12.     }  
13. }  
14. static void merge(int arr[], int l, int c, boolean d)  
15. {  
16.     int k,i;  
17.     if (c>1)  
18.     {  
19.         k = c/2;  
20.         for (i=l; i<l+k; i++)  
21.             exchange(arr, i, i+k, d);  
22.         merge(arr, l, k, d);  
23.         merge(arr, l+k, k, d);  
24.     }  
25. }  
26. static void bitonicSort(int arr[],int l, int c, boolean d)  
27. {  
28.     int k;  
29.     if (c>1)  
30.     {  
31.         k = c/2;  
32.         bitonicSort(arr, l, k, true);  
33.         bitonicSort(arr, l+k, k, false);  
34.         merge(arr,l, c, d);  
35.     }  
36. }  
37.    
38. static void sort(int arr[], int n, boolean order)  
39. {  
40.     bitonicSort(arr,0, n, order);  
41. }  
42. public static void main(String[] args)  
43. {  
44.     int arr[]= {1, 10, 2, 3, 1, 23, 45, 21};  
45.     int n = arr.length;  
46.     int i;  
47.     boolean order = true;     
48.     sort(arr, n, order);  
49.    
50.     System.out.println("Sorted array: \n");  
51.     for (i=0; i<n; i++)  
52.         System.out.println(arr[i]);  
53. }  
54. }  

Output:

Sorted array: 

1 1 2 3 10 21 23 45 

C#

1. //this program works when size of input is power of 2.   
2. using System;  
3. public class BitonicSort  
4. {  
5. static void exchange(int[] arr, int i, int j, bool d)  
6. {  
7.     int temp;  
8.     if (d==(arr[i]>arr[j]))  
9.     {  
10.             temp = arr[i];  
11.         arr[i] = arr[j];  
12.         arr[j] = temp;  
13.     }  
14. }  
15. static void merge(int[] arr, int l, int c, bool d)  
16. {  
17.     int k,i;  
18.     if (c>1)  
19.     {  
20.         k = c/2;  
21.         for (i=l; i<l+k; i++)  
22.             exchange(arr, i, i+k, d);  
23.         merge(arr, l, k, d);  
24.         merge(arr, l+k, k, d);  
25.     }  
26. }  
27. static void bitonicSort(int[] arr,int l, int c, bool d)  
28. {  
29.     int k;  
30.     if (c>1)  
31.     {  
32.         k = c/2;  
33.         bitonicSort(arr, l, k, true);  
34.         bitonicSort(arr, l+k, k, false);  
35.         merge(arr,l, c, d);  
36.     }  
37. }  
38.    
39. static void sort(int[] arr, int n, bool order)  
40. {  
41.     bitonicSort(arr,0, n, order);  
42. }  
43. public void Main()  
44. {  
45.     int[] arr= {1, 10, 2, 3, 1, 23, 45, 21};  
46.     int n = arr.Length;  
47.     int i;  
48.     bool order = true;     
49.     sort(arr, n, order);  
50.    
51.     Console.WriteLine("Sorted array: \n");  
52.     for (i=0; i<n; i++)  
53.         Console.WriteLine(arr[i]+"  ");  
54. }  
55. }