  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.
