Bitonic sort is a parallel sorting algorithm devised by Ken Batcher. A sequence of numbers from a(1), a(2), a(3), …, a(n) is called monotonic increasing or decreasing, if a(i) >= a(i+1) or a(i) <= a(i+1) respectively for all i equals 1,2,3,…, n-1. Sequence is monotonic if it is either monotonic increasing or monotonic decreasing.
A bitonic sequence is one that is monotonically increasing (or decreasing) up to some point where it reaches the maximum (or minimum) value of the sequence, and then it becomes monotonically decreasing (or increasing) up to the end. A sequence that can be converted to the aforementioned bitonic sequence by cyclic shifting is also called a bitonic sequence.
Given a bitonic sequence, bitonic split is an operation on it which scans for i equals 1 to n/2, and if a(i+n/2) < a(i) then swap a(i+n/2) and a(i). This operation produces two bitonic subsequences say L and R where L and R are left and right parts of the transformed sequence and all elements...