  This paper studies the average complexity on the number of comparisons for
sorting algorithms. Its information-theoretic lower bound is $n \lg n - 1.4427n
+ O(\log n)$. For many efficient algorithms, the first $n\lg n$ term is easy to
achieve and our focus is on the (negative) constant factor of the linear term.
The current best value is $-1.3999$ for the MergeInsertion sort. Our new value
is $-1.4106$, narrowing the gap by some $25\%$. An important building block of
our algorithm is "two-element insertion," which inserts two numbers $A$ and
$B$, $A<B$, into a sorted sequence $T$. This insertion algorithm is still
sufficiently simple for rigorous mathematical analysis and works well for a
certain range of the length of $T$ for which the simple binary insertion does
not, thus allowing us to take a complementary approach with the binary
insertion.

Data Structures and Algorithms