Bitonic sort
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 ...
Get OpenCL Programming by Example now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.