Bitonic Sort 介绍
Bitonic Sort
双调排序（Bitonic Sort）是一种支持并行运算的排序方式，全程只依赖于简单的比较和交换，很适合在具有大量并行执行单元如 GPU, NPU 等架构上对大量元素进行排序。
排序的流程大致分为两步。第一步从上到下将数组拆分成双调序列，第二步从下到上逐级合并成一个单调序列。下面会分别介绍什么是双调序列以及拆分-合并的流程。
双调序列（Bitonic Sequence）
双调序列指的是由一系列的数字，先单调递增后单调递减（或者先单调递减再单调递增）组成的序列。例如下列三组数据都可以称作双调序列。
- 递增递减数据量相同
[1, 4, 5, 6, 3, 2]：↗↘ (1, 4, 5) 递增， (6, 3, 2) 递减[8, 2, 1, 3]：↘↗↘↗ (8, 2) 递减，(1, 3) 递增 - 递增递减数据量不同
[1, 2, 4, 7, 6, 3]：↗↘ (1, 2, 4, 7) 递增， (6, 3) 递减 - 递增递减数据为 0
[1, 2, 3]：↗(1, 2, 3) 递增，()递减[6]：↗(6) 递增，()递减 [或者 ↘() 递增，(6)递减]
通过上面的三组双调序列可以总结出双调序列的定义（以先递增后递减为例）：一个序列 nums，存在一个 index ，对于所有 index 小于等于 的所有元素nums[:i]是单调递增的，所有 index 大于等于 的所有元素nums[i:]单调递减的，则称该序列为双调序列。
比较和交换（compare & swap)
比较和交换贯穿双调排序的流程，全程需要进行多次该操作。对于 nums[i] 和 nums[j] 这两个需要比较的数，在递增序列和递减序列的处理逻辑定义为：
nums[i]和nums[j]处于递增序列nums[i] > nums[j]->swap(nums[i], nums[j])nums[i] <= nums[j]->do nothing
nums[i]和nums[j]处于递减序列nums[i] < nums[j]->swap(nums[i], nums[j])nums[i] >= nums[j]->do nothing
创建一系列双调序列
根据双调序列的定义，我们可以将任意一组数据拆分成一系列双调序列的组合。为了方便展示，先不考虑奇数的场景。
以 [3, 6, 5, 7, 4, 1, 8, 2] 作为例子，先将其对半拆分：
[3, 6, 5, 7]，[4, 1, 8, 2]，再将每一部分对半拆分：
[3, 6]，[5, 7]，[4, 1]，[8, 2]，再将每一部分对半拆分：
[3]，[6]，[5]，[7]，[4]，[1]，[8]，[2]。
依据双调序列中第三类例子（递增递减数据为 0）可以将这一组数据看成是一系列递增、递减的序列组合。 
双调组合（Bitonic Merge）
双调组合是双调排序中的第二步，它的作用是将双调序列组（Bitonic Sequences）组合成一个新的单调序列组，最终不断组合成为一个单调的序列（单调的序列也是一个双调序列）。需要注意的是，每次 Merge 的序列必须是双调序列，单次 Merge 完之后的结果一定是严格单调。还是以 [3, 6, 5, 7, 4, 1, 8, 2] 作为例子，由于上述已经将其拆分成 8 个单调序列组。所以
- 第一步：两两组合成 4 个双调序列，Merge 变成 4 个单调序列，即 8 个 1 组合成 4 个 2；
- 第二步：将 4 个单调序列组合成 2 个双调序列，Merge 变成 2 个单调序列，即 4 个 2 组合成 2 个 4；
- 第三步：将 2 个单调序列组合成 1 个双调序列，Merge 变成 1 个单调序列，即 2 个 4 组合成 1 个 8。
组合的规则是在第 n 次 Merge 时，规定结果升序（ascend），在第 n+1 次 Merge 时，规定结果降序（descend）。将双调序列一分为二，逐位比较，按照 compare & swap 中提到的规则按照升（或者降）序进行比较和交换。再对交换完成的每一半再次一分为二，仍然按照升（或者降）序进行比较交换，再对剩余的进行一分为二，直至切分到最小比较单元为止。最终组合起来即为结果。
最小比较单元：指的是只有两个数进行比较的情况，因为再往下拆分成一个数没有比较的必要。
Merge 1 to 2
对于输入的数据，从左到右两两组合，[3] [6]，[5] [7]，[4] [1]，[8] [2]，按照组合的规则 「在第 n 次 Merge 时，规定结果升序（ascend），在第 n+1 次 Merge 时，规定结果降序（descend）」。
第 1 次、第 3 次 Merge 保持升序
根据比较和交换的规则，在递增序列中，如果 a > b 则交换 a, b， 如果 a <= b 则保持不变。所以在 3 和 6 比较时，保持不变。 4 和 1 比较时进行交换。由于此时已经时最小比较单元，则不必再向下拆分。 
第 2 次，第 4 次 Merge 保持降序
根据比较和交换的规则，在递减序列中，如果 a < b 则交换 a, b， 如果 a >= b 则保持不变。所以在 8 和 2 比较时，保持不变。 5 和 7 比较时进行交换。由于此时已经时最小比较单元，则不必再向下拆分。 
合并结果
此时 Merge 后的结果是 [3, 6] [7, 5] [1, 4] [8, 2]。
Merge 2 to 4
依旧对于输入的数据 [3, 6] [7, 5] [1, 4] [8, 2] 从左到右两两组合，按照组合的规则 「在第 n 次 Merge 时，规定结果升序（ascend），在第 n+1 次 Merge 时，规定结果降序（descend）」。
第 1 次 Merge 保持升序
在递增序列中，3 和 7 保持不变，6 和 5 进行交换，得到[3, 5, 7, 6]，当前的结果不是最小比较单元，则进行 2 次 SubMerge，将序列切一半后继续 Merge。在 SubMerge 中，3 和 5 进行比较，保持不变；7 和 6 进行交换。最终得到结果[3, 5, 6, 7]。 
第 2 次 Merge 保持降序
在递减序列中，4 和 2 保持不变，1 和 8 进行交换，得到 [8, 4, 1, 2]，当前的结果不是最小比较单元，则进行 2 次 SubMerge，将序列切一半后继续 Merge。在 SubMerge 中，8 和 4 进行比较，保持不变；1 和 2 进行交换。最终得到结果 [8, 4, 2, 1]。 
合并结果
此时 Merge 后的结果是 [3, 5, 6, 7] [8, 4, 2, 1]。
Merge 4 to 8
对于 [3, 5, 6, 7] [8, 4, 2, 1] 这个双调序列，逐位比较。由于只剩一次 Merge 了，那么这一次 Merge 保持升序。
升序 Merge
按照递增的交换规则，第一次 Merge 的时候，3 和 8 保持不变，5 和 4，6 和 2，7 和 1 需要进行交换。当前的结果不是最小比较单元，则进行 2 次 SubMerge，对于 [3, 4, 2, 1]，3 和 2，4 和 1 需要交换。对于 [8, 5, 6, 7]，8 和 6 需要交换。SubMerge 完成后，仍然不是最小比较单元，则对于每个 SubMerge，再次进行 2 次 SubMerge，2 和 1，6 和 5，8 和 7 需要交换。 
合并结果
此时 Merge 后的结果是 [1, 2, 3, 4, 5, 6, 7, 8]。
这样一来，经过 3 次的 Merge 和多次 SubMerge，可以得到一个单调有序的序列。
优缺点
- 优点: 支持并行；排序效率高（时间复杂度低）；支持分块（tile）计算这种场景。
- 缺点：在非并行的场景执行速度会变低；对于输入数据量有要求（n = 2^k）；算法实现起来较为复杂。