双调排序

双调排序是一种并行排序算法，如果以串行的方式运行，其复杂度为$$O(n\log^2n)$$，相对地，如果有$$n$$个可同时运行的线程，则复杂度为$$O(\log^2n)$$。

首先介绍双调序列。所谓单调序列，就是指一个递减或者递增序列，而双调，就是将两个长度相同，单调性相反的序列连接起来的序列，如果画成图形就是以下两种序列：

对于这样一个序列，可以设计一个输入和输出个数为$$2^k$$的排序网络，对$$2^k$$个数进行排序，其网络结构如下：

这个网络共有16个输入，其中每一条连线代表一次比较。可以看出，输入为$$2^k$$的排序网络总共有$$k$$个部分，第$$i$$个部分完成对规模为$$2^{k-i+1}$$的数据的比较。

首先，输入第一部分的序列是一个先增后减的双调序列，第一部分的比较网络会将这个序列分为两个子序列，而且前半部分子序列中的每一个数都小于后半部分中的数，这是由比较前两个子序列的单调性决定的。

然后，比较网络的第二部分对上回输出的每个子序列再次进行相同的操作。网上好多人都说因为这个序列仍然是双调的所以继续下去，双调性可以保持云云，但这个说法是完全错误的！因为再进行下去的序列完全有可能变成不是双调的。（不过下面有评论说我双调的定义有误，所以双调性其实可以保持）下面举个例子说明：

• 初始值：(10 11 13 14 15 16 17 18 19 15 13 12 12 11 9 8)
• (10 11 13 14 15 16 17 18) (19 15 13 12 12 11 9 8) 网络1排序→ (10 11 13 12 12 11 9 8) (19 15 13 14 15 16 17 18)
• (10 11 13 12) (12 11 9 8) (19 15 13 14) (15 16 17 18) 网络2排序→ (10 11 9 8) (12 11 13 12) (15 15 13 14) (19 16 17 18)
• (10 11) (9 8) (12 11) (13 12) (15 15) (13 14) (19 16) (17 18) 网络3排序→ (9 8) (10 11) (12 11) (13 12) (13 14) (15 15) (17 16) (19 18)
• 最终结果：(8 9 10 11 11 12 12 13 13 14 15 15 16 17 18 19)

其中出现了(12 11 13 12)这个非双调的序列，但是结果正确。网上流行的“每个子序列都是双调序列”的说法完全是错误的。

阅读《算法导论》，发现正确性证明确实是用到了保持双调性的性质，但是并非直接得到。

引理：对于单调增函数$$f(x)$$，若任意比较网络输入$$<x_1,x_2,\cdots,x_n>$$时，输出$$<x_{k_1},x_{k_2},\cdots,x_{k_n}>$$，则输入$$<f(x_1),f(x_2),\cdots,f(x_n)>$$时，会输出$$<f(x_{k_1}),f(x_{k_2}),\cdots,f(x_{k_n})>$$。

证明：因为$$f(x)$$单调增，所以通过比较网络中某一比较器时，若$$x_1>x_2$$，则$$f(x_1)>f(x_2)$$，反之亦然。

定理：对于排序网络来说，只要可以对0,1序列进行排序，即可对任意序列排序。

证明：若排序结果（递减排序）出现了$$a_i>a_j$$而$$a_i$$在$$a_j$$之前的情况，那么定义$$f(x)=0, x&lt;a_i; f(x)=1, x\geq a_i$$，使用上述引理得出这个网络不能给0,1序列排序。矛盾。

所以我们只需要证明双调排序对0,1序列有效即可，而对于0,1序列，易证明经过每一部分之后的子序列总是可以保证双调性的，从而证明了排序是有效的。

那么如何从无序序列得到双调序列呢？可以使用排序的方式。因为长度为2的序列一定是双调序列，通过构造以下的网络，就可以完成从无序序列到双调序列的转换：

其中灰色的比较器表示比较方向和白色的比较器相反，这样才可以形成一个反向有序的序列。

至此，双调排序已经完整说明。