In computer science, a sorting network is an abstract description of how to sort a fixed number of values i.e. how the values are compared and exchanged.
This can be represented graphically, by having each input value as a horizontal line, and each compare and exchange unit as a vertical connection between those lines.
There are various examples of sorting networks in the literature, but we concentrate our description on the Bitonic sort [1]}.
This network is easy to implement and has an algorithm complexity of O(n log(n)\(^2\)  ).
It has demonstrated good performances on parallel computers [2]} and GPUs [3]}.
Figure REF (a) shows a Bitonic sorting network to process 16 values.
A sorting network can be seen as a timeline, where input values are transferred from left to right, and exchanged if needed at each vertical bar.
We illustrate an execution in Figure REF (b), where we print the intermediate steps while sorting an array of 8 values.
We use the terms symmetric and stair exchanges to refer to the red and orange stages, respectively.
A symmetric stage is always followed by stair stages from half size to size two.
The Bitonic sort does not maintain the original order of the values and thus is not stable.
<FIGURE>