Bitonic Sort 双调排序 • CoderXL's Blog

Bitonic 似乎是一个双关，既表示 bi + tonic “双调”，即先增后减或先减后增，又可以理解为 bit + onic “关于二进制位的”，提示了里面使用了很多位运算优化。

概述#

由于这个算法是专门为数据并行处理而设计的，可以做到同一层排序内的比较和交换互不依赖，因此只有在并行计算框架下才能发挥出其完全性能。当串行处理时，其复杂度不是最优的，达到了 $O(n\log^2 n)$ ，但由于每一层可以完全并行，所以在并行框架下可以达到 $O({n\over p}\log^2 n)$ .

这个算法类似归并，但将归并中的“合并”（代价 $O(n)$ ）这一无法并行的操作（双指针步进互相依赖，无法预测）替换为了可以并行的“双调合并”（代价 $O(n\log n)$ ，可以并行到 $O({n\over p}\log n)$ ）。

具体地，它有两个递归的任务：

将一段双调序列变为一段单调序列
将两段相邻的单调性不同的单调序列拼成一段更长的双调序列

为了严谨讨论，我们约定：双调序列的长度为 2 的幂，其前半段递增（递减），后半段递减（递增），并称其为“凸的”（“凹的”）。

刚刚的任务中，1. 自身可以递归 $\log n$ 次完成。具体地，当当前双调序列长度为 $2n$ 时，每次依次比较 $a[i]$ 和 $a[i+n]$ ，其中 $i\in[1,n]$ ，通过必要的交换保证 $a[i]\ \mathrm{op}\ a[i+n]$ ，其中 $\mathrm{op}\in \{\le, \ge\}$ . 经过操作之后，这个双调序列会变成两个相邻的、凸凹性相反的双调序列，其中凸的序列中的元素都小于等于凹的序列中的元素。这就形成了 $[1,n]$ 和 $[n+1,2n]$ 这两个区间之间的单调性。继续递归直到 $n=1$ ，此时将会变成单调序列。