Insertion sort is very efficient for sorting a small number of elements. It is so fast, that many divide-and-conquer sort algorithms (e.g. merge and quick sort) switch to insertion sort when the group size is small. However, one important, but not obvious question, is what’s the right group size to convert when the algorithm should switch insertion sort?
The above chart shows the performance of quicksort and insertion sort on sorting random 32-bit real numbers (on Fortran 95). The data suggests the algorithm should switch to insertion sort when the number of elements is less that 190. However, the combined effect of the two sort methods running together may produce different results.
The above chart shows the optimal insertion size is far less than 190. The algorithm should switch to insertion sort only when the number of elements is below about 50. This result is surprising and shows the synergy between the two sort methods. Also, these results are for arrays of 32-bit values. If the sorted elements are larger, then the CPU cache could store less of them, the insertion size limit will shrink. Study into individual cases will be necessary to determine the ideal size for special data elements.
The chart also shows the magnitude of improvement the insertion-quicksort combo algorithm provides over plain quicksort. For small number of elements (~100 elements) the improvement is more than halving the execution time. For one million elements the improvement is still a meaningful 30% execution time reduction.
The following examples were run in using Fortran 95 and single-threaded.