用FPGA实现双调排序（4）

前面三篇文章我们介绍了双调排序的原理和具体实现方式，但都是要求序列本身是“双调”的。而实际情况是，给定序列本身是杂乱无章的，并非呈现“双调”的特征。这就要求我们先把无序序列转化为双调序列。但无需担心，这种转化也是有章可循的。

我们仍以16点序列为例，如下图所示。16点序列转化为双调序列需要3个Stage，其实Stage的个数等于log2(16)-1。每个Stage需要完成一些列的比较，其实就是实现升序和降序排列。例如，在Stage 0，每两个数据一组，按“升序->降序”的方式排列。图中圆圈内“+”表示升序，因此输入为10和20时，输出为10和20；圆圈内为“−”表示降序，因此输入为5和9时，输出为9和5。同时注意到所有的比较都是原位运算，即输入数据和输出数据对应的地址是一致的。例如，Stage 0输入5和9，分别在2号和3号地址上，输出9和5仍然继续保持在2号和3号地址上。

进一步分析，我们将每个Stage操作用到的数据对应的地址提取出来形成如下表格，从中可以发现如下特征：

（1）每个Stage升序和降序操作的个数是一致的。例如：Stage 0要做4次升序排序，也要做4次降序排列，Stage 1亦是如此。图中“↓”表示升序排列，“↑”表示降序排列，即箭头总是指向较大的数。

（2）每个Stage操作数对应的地址间隔step为2^Stage。例如：Stage 0其中两个操作数分别来自于0号地址和1号地址，地址间隔为1，即2^0；Stage 1其中两个操作数分别来自于0号和2号地址，地址间隔为2，即2^1。

（3）每个Stage要执行Round轮次比较，每轮要执行N/2次比较。这里Round为Stage+1，N为序列长度。例如：Stage 0比较1轮，Stage 1比较2轮，每轮都比较8次，Stage 2比较3轮，每轮也是比较8次。

根据上述分析，我们可以将Stage、step、Round之间的关系用如下表格表示。表中m为Round的可取值。从循环的角度看，Stage为最外层循环，Round对应中间循环，Round内部的N/2次比较对应最内层循环。根据这个表格也可以看出step可以用Stage和m表示为2^(Stage-m)。

我们将双调序列的排序过程再次呈现出来如下图所示，与本文第一张图片进行对比，可以发现：从“无序”到“双调”是一个序列合并的过程，从“双调”到“单调”是一个序列分割的过程，体现了“分而治之（Divide and Conquer）”的思想。