不同于2^n大小的最优Batcher奇偶合并网络

Question

最近，我一直在尝试使用最少的比较-交换单元（按大小而非深度最优）实现大小为32的排序网络。目前，我已经能够使用以下资源生成我的网络：

• 0到16个排序网络：Perl的Algorithm::Networksort模块，使用“Best”算法。不幸的是，它只提供了已知的最佳网络，直到大小为16。

• 17到23个排序网络：使用对称性和进化搜索来最小化排序网络，作者是Valsalam和Miikkulainen。

Baddar的论文寻找更好的排序网络给出了已知需要排序网络0到32的最小比较-交换单元数（不是最新的，因为Valsalam和Miikkulainen为大小为17、18、19、20、21和22的网络提供了更好的算法），以及用于找到它们的方法：基本上，必须将要排序的数组分成两部分，然后使用这些大小的最佳已知排序网络对两个半部分进行排序，然后使用奇偶合并网络（对应于Batcher的奇偶合并排序的合并步骤）将它们合并。

维基百科页面为Batcher的奇偶合并排序给出了以下Python实现：

def oddeven_merge(lo, hi, r):
    step = r * 2
    if step < hi - lo:
        yield from oddeven_merge(lo, hi, step)
        yield from oddeven_merge(lo + r, hi, step)
        yield from [(i, i + r) for i in range(lo + r, hi - r, step)]
    else:
        yield (lo, lo + r)

def oddeven_merge_sort_range(lo, hi):
    """ sort the part of x with indices between lo and hi.

    Note: endpoints (lo and hi) are included.
    """
    if (hi - lo) >= 1:
        # if there is more than one element, split the input
        # down the middle and first sort the first and second
        # half, followed by merging them.
        mid = lo + ((hi - lo) // 2)
        yield from oddeven_merge_sort_range(lo, mid)
        yield from oddeven_merge_sort_range(mid + 1, hi)
        yield from oddeven_merge(lo, hi, 1)

def oddeven_merge_sort(length):
    """ "length" is the length of the list to be sorted.
    Returns a list of pairs of indices starting with 0 """
    yield from oddeven_merge_sort_range(0, length - 1)

oddeven_merge 步骤已经被隔离，所以很容易单独使用它来生成合并原始数组的两个排序后半部分所需的索引对。但是，此实现仅在数组大小为2的幂时才起作用。因此，它只允许我找到大小为32的排序网络所需的最小已知比较交换单元数量。删除具有最高索引的索引对使我能够找到相当于大小为31的排序网络，但是删除更多的索引对并没有产生最佳已知结果，适用于小于31的尺寸。

Perl 的 Algorithm::Networksort 模块提供了一种替代 Batcher 奇偶合并排序实现方法，可以处理任何大小的数组，而不仅仅是2的幂。因此，我决定查看它，看看是否可以从算法中提取合并步骤。以下是 Python 等效代码（也符合 Knuth 在《计算机程序设计艺术第3卷》中描述的算法）：

def oddeven_merge_sort(length):
    t = math.ceil(math.log2(length))

    p = 2 ** (t - 1)

    while p > 0:
        q = 2 ** (t - 1)
        r = 0
        d = p

        while d > 0:
            for i in range(length - d):
                if i & p == r:
                    yield (i, i + d)

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

很遗憾，这个算法对我来说有点晦涩难懂，我无法从中提取合并部分。我成功构建了一个合并网络，为24个单位大小的排序网络给出了最小已知的比较交换数，但我所使用的技巧无法扩展到任何其他大小（并且据我的理解，它绝对不是奇偶合并）。我尝试了更多的方法来适应Batcher的奇偶排序算法的合并步骤，但我无法找到25、26、27、28、29和30个单位大小的最佳已知排序网络。如何派生这个合并步骤以找到拼图中缺失的部分呢？

- Morwenn

Answer 1

Perl算法 在评论中提到 它是Knuth的《搜索与排序》中的算法5.2.2M。

反过来，Knuth提到当 p = 1 时，它将已排序的序列合并在一起。因此，要生成任何N的序列并合并其对，只需使用 p = 1 运行该算法：

def oddeven_merge_step(length):
    t = math.ceil(math.log2(length))
    q = 2 ** (t - 1)
    r = 0
    d = 1

    while d > 0:
        for i in range(length - d):
            if i & 1 == r:
                yield (i, i + d)

        d = q - 1
        q //= 2
        r = 1

请注意，Batcher的奇偶合并步骤期望排序后的序列是交错的（偶数，奇数，偶数，...），但生成的排序序列是连续的。例如，对于N = 25，它会生成以下网络：

- orlp