In order to improve the speed at which the insertion sort runs for
nonbestcase data sets it is possible to use a binary search in order
to place item number n into the n1 sorted items. This leads to a
drastic reduction in number of comparisons; each binary search takes
only log_{2} n comparisons and each of the n items must be inserted
leading to a total of n log_{2} n comparisons. However, the number of
data move operations will remain unchanged. Thus even the improved
insertion sort is deemed a quadratic algorithm.
