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

Question

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

• Sedgewick R.的一本书
• 这个SO问题

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

这是一个具有32个输入的生成网络的图像。在两条水平线之间的垂直线表示比较值a[x]和a[y]，如果大于则交换数组中的值。

_{(来源：flylib.com)}
(可点击)

我从Java代码复制了C代码，并用printf函数替换了exch函数以打印交换的候选项。

当人们绘制对数图时，可以看出生成了太多的对。

有人知道如何修复这个算法吗？

我为什么需要非递归版本？
我想将这个排序网络转换成硬件。在非递归算法中插入管道阶段很容易。

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

我的C代码：

#include <stdlib.h>
#include <stdio.h>

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

  for (int p=1; p<n; p+=p)
    for (int k=p; k>0; k/=2)
      for (int j=k%p; j+k<n; j+=(k+k))
        for (int i=0; i<n-j-k; i++)
          if ((j+i)/(p+p) == (j+i+k)/(p+p))
              printf("%2i cmp %2i\n", l+j+i, l+j+i+k);
}
int main(char* argv, int args)
{ const int COUNT = 8;
  sort(0, COUNT);
}

结果：

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

---

附录:
奇偶归并排序（也称为Batcher's sort）类似于比特位排序（不要与Batcher的比特位排序混淆）。但在硬件中，这种算法具有比比特位排序更好的规模复杂度，而延迟相同。

与快速排序等快速软件算法相比，这些算法可以使用较少的资源。

维基百科：奇偶归并排序

注意:
由于排序网络是静态的且独立于输入值，因此不需要比较和交换即可生成网络。这是它可以转换为硬件的原因之一。我的代码生成用于比较操作的索引。在硬件中，这些垂直连接将被比较和交换电路替换。因此，未排序的数据将通过网络传输，在输出端它将被排序。

- Paebbels

---

不确定您对效率的要求有多高，但如果最终结果准确，那么在过程中生成太多的配对是否真的很重要呢？ - MaxOvrdrv

在软件中，它会生成大量的比较操作，并造成缓存污染。在硬件中，它会增加面积消耗和延迟。通常，奇偶归并排序具有O（N * log N * log N）的大小复杂度。我的图表看起来像N的立方。 - Paebbels

也许这可以帮助？http://www.academia.edu/9035484/VLSI_Design_of_Parallel_Sorter_based_on_Modified_PCM_Algorithm_and_Batchers_Odd-Even_Mergesort。请尝试http://dsp.stackexchange.com/。 - some_id

我用ASCII艺术完成了我的结果图表 :) - Paebbels

谢谢，Paebbels。现在问题更清楚了。第二列中的2-3、4-5和6-7排序显然是多余的。 - David Grayson

Answer 1

以下代码适用于任意大小的数组，且不使用递归。它是从 Perl 的 Algorithm::Networksort 模块中 相应函数 的实现直接移植而来。该实现恰好对应 Knuth 在《计算机程序设计艺术》第三卷中描述的算法（算法 5.2.2M）。它不能帮助您实际修复算法，但至少为您提供了一个仅有三个嵌套循环的工作非递归实现 Batcher 奇偶归并排序的方法 :)

#include <math.h>
#include <stdio.h>

void oddeven_merge_sort(int length)
{
    int t = ceil(log2(length));
    int p = pow(2, t - 1);

    while (p > 0) {
        int q = pow(2, t - 1);
        int r = 0;
        int d = p;

        while (d > 0) {
            for (int i = 0 ; i < length - d ; ++i) {
                if ((i & p) == r) {
                    printf("%2i cmp %2i\n", i, i + d);
                }
            }

            d = q - p;
            q /= 2;
            r = p;
        }
        p /= 2;
    }
}

如果你能得到《计算机程序设计艺术第三卷》的副本，你将会得到关于算法如何以及为什么工作的很好的解释，还有一些额外的细节。

- Morwenn

---

我会尝试在图书馆找到这本书。 - Paebbels

Answer 2

这是一个固定的非递归子程序。

void sort(int n)
{
  for (int p = 1; p < n; p += p)
    for (int k = p; k > 0; k /= 2)
      for (int j = k % p; j + k < n; j += k + k)
        //for (int i = 0; i < n - (j + k); i++) // wrong
        for (int i = 0; i < k; i++) // correct
          if ((i + j)/(p + p) == (i + j + k)/(p + p))
            printf("%2i cmp %2i\n", i + j, i + j + k);
}

或者

void sort(int n)
{
  for (int p = 1; p < n; p += p)
    for (int k = p; k > 0; k /= 2)
      for (int j = 0; j < k; j++)
        for (int i = k % p; i + k < n; i += k + k)
          if ((i + j)/(p + p) == (i + j + k)/(p + p))
            printf("%2i cmp %2i\n", i + j, i + j + k);
}

- wkpark

Answer 3

我想我找到了一个解决方案。我检查了length = 2, 4, 8, 16。

这是我的代码：

void sort(int length)
{ int G = log2ceil(length);                      // number of groups
  for (int g = 0; g < G; g++)                    // iterate groups
  { int B = 1 << (G - g - 1);                    // number of blocks
    for (int b = 0; b < B; b++)                  // iterate blocks in a group
    { for (int s = 0; s <= g; s++)               // iterate stages in a block
      { int d = 1 << (g - s);                    // compare distance
        int J = (s == 0) ? 0 : d;                // starting point
        for (int j = J; j+d < (2<<g); j += 2*d)  // iterate startpoints
        { for (int i = 0; i < d; i++)            // shift startpoints
          { int x = (b * (length / B)) + j + i;  // index 1
            int y = x + d;                       // index 2
            printf("%2i cmp %2i\n", x, y);
          }
        }
      }
   }
}

这个解决方案引入了第五个for循环来处理组内的子块。 j循环具有更改的起始和中止值，以处理奇数后合并步骤的计数，而不会生成重复的比较步骤。

- Paebbels