  We study the impact of merging routines in merge-based sorting algorithms.
More precisely, we focus on the galloping routine that TimSort uses to merge
monotonic sub-arrays, hereafter called runs, and on the impact on the number of
element comparisons performed if one uses this routine instead of a na\"ive
merging routine.
  This routine was introduced in order to make TimSort more efficient on arrays
with few distinct values. Alas, we prove that, although it makes TimSort sort
array with two values in linear time, it does not prevent TimSort from
requiring up to $\Theta(n \log(n))$ element comparisons to sort arrays of
length~$n$ with three distinct values. However, we also prove that slightly
modifying TimSort's galloping routine results in requiring only $\mathcal{O}(n
+ n \log(\sigma))$ element comparisons in the worst case, when sorting arrays
of length $n$ with $\sigma$ distinct values.
  We do so by focusing on the notion of dual runs, which was introduced in the
1990s, and on the associated dual run-length entropy. This notion is both
related to the number of distinct values and to the number of runs in an array,
which came with its own run-length entropy that was used to explain TimSort's
otherwise "supernatural" efficiency. We also introduce new notions of fast- and
middle-growth for natural merge sorts (i.e., algorithms based on merging runs),
which are found in several merge sorting algorithms similar to TimSort.
  We prove that algorithms with the fast- or middle-growth property, provided
that they use our variant of TimSort's galloping routine for merging runs, are
as efficient as possible at sorting arrays with low run-induced or
dual-run-induced complexities.
