next up previous contents index Search
Next: Source Code Up: 0.3.5 Insertion Sort Previous: Analysis Improvements

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.

Scott Gasch