what is Bitonic Sort?
GIAN Tutorials
11:20 PM
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, 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
