如何修复这种非递归奇偶合并排序算法？

我正在寻找非递归奇偶合并排序算法,并找到了两个来源:

一本来自Sedgewick R.的书.

这个问题

两种算法都相同但是错误.生成的排序网络不是奇偶合并排序网络.

以下是具有32个输入的结果网络的图像.2条水平线之间的垂直线表示将值a [x]与[y]进行比较,如果大于,则交换数组中的值.

32个输入的奇偶合并排序http://flylib.com/books/3/55/1/html/2/images/11fig07.gif(可点击)

我将代码从Java复制到C并用excha 替换了函数printf来打印交换候选者.

当绘制对的图时,可以看出生成了太多对.

有谁知道如何修复此算法？

为什么我需要非递归版本？
我想将这个排序网络转换为硬件.将流水线阶段插入非递归算法很容易.

我还调查了递归版本,但是将算法转换为流水线硬件太复杂了.

我的C代码:

#include 
#include 

void sort(int l, int r)
{ int n = r-l+1;

  for (int p=1; p0; k/=2)
      for (int j=k%p; j+k

结果:

0 -o--------o-------------------------o---------------o-------------------------
   |        |                         |               |
1 -o--------|-o------o----------------|-o-------------o-o-----------------------
            | |      |                | |               |
2 -o-o------o-|------o-o--------------|-|-o----o--------o-o---------------------
   | |        |        |              | | |    |          |
3 -o-o--------o--------o--------------|-|-|-o--|-o--------o-o-------o-----------
                                      | | | |  | |          |       |
4 -o-o-o----o---o----o-----o----------o-|-|-|--o-|-o--------o-o-----o-o---------
   | | |    |   |    |     |            | | |    | |          |       |
5 -o-o-o----|-o-|-o--o-o---o-o---o------o-|-|----o-|-o--------o-o-----o-o---o---
            | | | |    |     |   |        | |      | |          |       |   |
6 -o-o-o-o--o-|-o-|----o-o---o-o-o-o------o-|------o-|----------o-o-----o-o-o-o-
   | | | |    |   |      |     |   |        |        |            |       |   |
7 -o-o-o-o----o---o------o-----o---o--------o--------o------------o-------o---o-


当我知道正确的交换对并且算法等于图像时,我会将其转换为VHDL以便在我的硬件平台上进行测试.

其他开源硬件排序网络实现:


PoC.sort.sortnet.oddevensort
PoC.sort.sortnet.bitonicsort




附录:
 
Odd-even mergesort(又名Batcher的排序)就像是bitonic排序(不要与Batcher的bitonic排序混淆).但是在硬件中,该算法具有比比特排序更好的大小复杂度,而延迟是相同的.

与诸如快速排序的快速软件算法相比,这些算法可以以良好的资源使用来实现.

维基百科:奇偶合并

注意:
 
由于排序网络是静态的并且与输入值无关,因此不需要比较和交换来生成网络.这就是它可以转化为硬件的一个原因.我的代码生成比较操作的索引.在硬件中,这些垂直连接将被比较和交换电路取代.因此,未排序的数据将通过网络传输,并且在输出端将对其进行排序.