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