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

Start Free Trial

No credit card required