并行排序算法：双调排序

引入

有一个排列，你可以通过“比较并交换”这个操作将该排列排好序，即，每次选择一对数 \((i,j)\)，若 \(a_i>a_j\) 则交换，否则不交换。

但是，你可以把多对 \((i,j)\) 放在一次操作里并行“比较并交换”，此时操作数记 1，与数对的对数无关，但是每个 \(i\) 只能出现至多一次。要求操作数最小。

定义

双调序列：先单增后单减，或者先单减后单增。即，单峰数列或单谷数列。

算法流程

定理：设一个长度为 \(2^k\) 的序列 \(\{a_i\}\)，将该序列劈成两半，然后将两个序列的对应位置 \((i,i+2^{k-1})\) 执行“比较并交换”，则操作结束后两个序列也都是双调序列。

考虑 01 序列，显然序列形如 001100 或者 110011，不妨设其为 001100，分类讨论一下中点落在哪即可。对于一般情况，对于所有 \(x\)，令 \(b_i\leftarrow [a_i\le x]\) 就转化为了 01 序列问题。

那么如果我们想要把一个双调序列排序的话，根据定理我们就可以将 \(2^k\) 的问题划分成两个 \(2^{k-1}\) 的独立子问题，递归下去即可。由于分治的每一层每个节点相互独立，所以双调序列排序可以在 \(O(\log n)\) 次操作内完成。

考虑将一般序列排序。还是考虑分治，假设我们已经将 \(a_{[1,2^{k-1}]},a_{(2^{k-1},2^k]}\) 排好序，那么将后一半序列翻转一下，就转化成了双调序列了。实现中，为了实现翻转，只需要把 \((i,i+2^{k-1})\) 操作变成 \((i,2^k-i+1)\) 即可。同理，每一层的点还是相互独立，一般序列排成双调序列也可以在 \(O(\log n)\) 的时间内完成。

故总操作次数为 \(O(\log^2n)\)。由于该排序常规时间复杂度 \(O(n\log^2n)\)，故在常规排序中不实用。