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

Question

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

排序网络 0 到 16：Perl 的 Algorithm::Networksort module 和 "Best" 算法。不幸的是，它只提供 16 号之前最知名的网络。
排序网络 17 到 23：Using Symmetry and Evolutionary Search to Minimize Sorting Networks 作者 Valsalam 和 Miikkulainen。

论文Finding Better Sorting Networks by Baddar gives the minimal number of compare-exchange units known to be needed for sorting networks 0 to 32 (not up-to-date since Valsalam and Miikkulainen provide better algorithms for the sizes 17, 18, 19, 20, 21 and 22) and the method used to find them: basically, one has to split the array to sort in two, then sort both halves using the best known sorting networks for these sizes before merging them using an odd-even merge network (which corresponds to the merge step of Batcher's odd-even mergesort).

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

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 在 The Art of Computer Programming vol. 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's Searching and Sorting中的算法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，它会生成以下网络：

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

Optimal Batcher odd-even merge networks for sizes different than 2^n

sorting

algorithm

merge

sorting-network