algorithm - 澄清排序网络大小的上限和下限

Question

引用这篇维基百科的文章:https://en.wikipedia.org/wiki/Sorting_network ，重点放在构建排序网络段落。

您能否解释一下Size, upper bound 和Size, lower bound(在表中)是什么？我希望 lower bound 指的是对 n 个数字的输入进行正确排序所需的最少连接数(我说得对吗？)。如果是这样，为什么还要为 upper bound 烦恼呢？理论上，可以使用大于 upper bound 的连接数，那么如何建立呢？我也阅读了链接的论文(引用文献 11)，但我仍然感到困惑。

Answer 1

表后的段落提示了上界和下界的含义:

For one to ten inputs, minimal (i.e. size-optimal) sorting networks are known, and for higher values, lower bounds on their sizes S(n) can be derived inductively using a lemma due to Van Voorhis: S(n + 1) ≥ S(n) + ⌈log2(n)⌉.

表中的“上限”显然对应于给定数量的待排序元素当前已知的最优化排序网络的大小。已知的 1 到 10 个元素的尺寸最优排序网络已经被证明是最优的，但是我们不确定已知的更多元素的尺寸最优排序网络实际上是否是最优的。 «下界»对应于排序网络对给定数量的元素进行排序的理论最小大小:可能不存在这种大小的排序网络，但我们尚未证明这一点。

总结:

• « 上限 » 表示已找到的尺寸最优化的排序网络。
• « 下界 » 代表网络的理论最小尺寸。目前还没有证明这样的网络不存在，但我们也没有找到任何这种规模的可行网络。

---

作为旁注，我维护 a library具有大小最优的排序网络，它们的大小对应于表中的“上限”(另请参见 the documentation 和 the implementation)。