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.

翻译：确定美元S(n)的最小比值是一个长期的未决问题,它足以对一系列美元要素进行分类。 事实上,在这项工作之前,美元S(n)美元只以美元=22美元为已知值,只有美元=16美元、17美元和18美元除外。 在这项工作中,我们通过对美元=16美元、17美元和18美元的比值分别进行分类来填补这一差距。这完全决定了这些值的美元S(n),并否定了Knuth的假设:美元S(16)=45美元。此外,我们表明,要对28美元元素进行分类,至少需要99美元的比较。我们通过彻底的计算机搜索来获取我们的结果,这种搜索将Wells(1965年)和Peczarski(2002年、2004年、2007年、2012年)的先前工作推延长,我们的进展既基于硬件的进步,也基于新的算法概念,例如对该问题进行双向搜索。