论文标题
排序16、17和18个要素的下限
Lower Bounds for Sorting 16, 17, and 18 Elements
论文作者
论文摘要
这是一个长期以来的公开问题，可以确定比较$ s（n）$的最小数量，足以对$ n $元素进行排序。的确，在此工作之前，$ s（n）$仅以$ n \ leq 22 $而闻名，但$ n = 16 $，$ 17 $和$ 18 $的例外。在这项工作中，我们通过证明排序$ n = 16 $，$ 17 $，和$ 18 $元素需要$ 46 $，$ 50 $和$ 54 $比较来填补这一空白。这完全确定了这些值的$ s（n）$，并反驳了Knuth的猜想，即$ s（16）= 45 $。此外，我们表明，对于对$ 28 $元素进行排序至少需要99个比较。我们通过详尽的计算机搜索获得结果，该计算机搜索扩展了Wells（1965）和Peczarski（2002，2004，2007，2012）的先前工作。我们的进步既基于硬件的进步和新颖的算法思想，例如将双向搜索应用于此问题。
It is a long-standing open question to determine the minimum number of comparisons $S(n)$ that suffice to sort an array of $n$ elements. Indeed, before this work $S(n)$ has been known only for $n\leq 22$ with the exception for $n=16$, $17$, and $18$. In this work, we fill that gap by proving that sorting $n=16$, $17$, and $18$ elements requires $46$, $50$, and $54$ comparisons respectively. This fully determines $S(n)$ for these values and disproves a conjecture by Knuth that $S(16) = 45$. Moreover, we show that for sorting $28$ elements at least 99 comparisons are needed. We obtain our result via an exhaustive computer search which extends previous work by Wells (1965) and Peczarski (2002, 2004, 2007, 2012). Our progress is both based on advances in hardware and on novel algorithmic ideas such as applying a bidirectional search to this problem.
