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

Question

这些天，我一直在尝试使用最少数量的比较交换单元实现大小为 32 的排序网络(在大小方面是最优的，而不是在深度方面) .截至目前，我已经能够使用以下资源来生成我的网络:

• 排序网络 0 到 16:Perl 的 Algorithm::Networksort module使用“最佳”算法。不幸的是，它只提供 16 号之前最知名的网络。

• 对网络 17 到 23 进行排序:Using Symmetry and Evolutionary Search to Minimize Sorting Networks作者:Valsalam 和 Miikkulainen。

论文Finding Better Sorting Networks Baddar 给出了排序网络 0 到 32 所需的已知比较交换单元的最小数量(不是最新的，因为 Valsalam 和 Miikkulainen 为大小 17、18、19、20、21 和 22 提供了更好的算法)以及用于找到它们的方法:基本上，必须将数组分成两部分进行排序，然后使用这些大小的最知名的排序网络对两半进行排序，然后使用奇偶合并网络(对应于合并Batcher's odd-even mergesort 的步骤)。

维基百科页面为 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 的奇偶合并排序的合并步骤，用于大小不是 2 的幂的数组，但我找不到大小为 25 的最著名的排序网络， 26、27、28、29 和 30。我怎样才能推导出这个合并步骤来找到拼图中缺失的部分？

Answer 1

Perl 算法 mentions in a comment它是 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，它会生成以下网络: