O'Reilly logo

OpenCL Programming by Example by Koushik Bhattacharyya, Ravishekhar Banger

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

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

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required