11.2. The bitonic sort

Algorithms that sort data form a vital part of any programmer’s repertoire, and no introductory computer science course could be complete without a discussion of bubble sorts, insertion sorts, and selection sorts. But as multicore processors gain in power and popularity, it becomes crucial to sort data using a parallelized algorithm. Some algorithms are better suited to parallel implementation than others, and the bitonic sort (also called the bitonic merge sort) is one of the few sorting methods that was designed to be implemented with multiple processing elements. The goal of this section is to explain how the bitonic sort works and how to implement it with OpenCL.

11.2.1. Understanding the bitonic sort

Most presentations of the bitonic sort proceed from start to finish, but I’d like to begin this discussion with the end goal. First, I’ll explain what bitonic sequence are and how they can be sorted. Then I’ll explain how to turn an unordered sequence into a bitonic sequence.