  MergeInsertion, also known as the Ford-Johnson algorithm, is a sorting
algorithm which, up to today, for many input sizes achieves the best known
upper bound on the number of comparisons. Indeed, it gets extremely close to
the information-theoretic lower bound. While the worst-case behavior is well
understood, only little is known about the average case.
  This work takes a closer look at the average case behavior. In particular, we
establish an upper bound of $n \log n - 1.4005n + o(n)$ comparisons. We also
give an exact description of the probability distribution of the length of the
chain a given element is inserted into and use it to approximate the average
number of comparisons numerically. Moreover, we compute the exact average
number of comparisons for $n$ up to 148.
  Furthermore, we experimentally explore the impact of different decision trees
for binary insertion. To conclude, we conduct experiments showing that a
slightly different insertion order leads to a better average case and we
compare the algorithm to the recent combination with (1,2)-Insertionsort by
Iwama and Teruyama.
