It is used for smaller size arrays. In Java Collections, insertion sort is applied to an array of size 7 or else. This cutoff is based on empirical studies. The best choice for the cutoff is actually machine ]dependent.
public void insertionSort(int x)
int off = 0, len = x.length;
for (int i = off; i < len; i++)
for (int j = i; j > off && x[j-1] > x[j]; j–)
swap(x, j, j-1);
public void swap (int x; int a, int b)
int t = x[a]; x[a] = x[b]; x[b] = t;
The outer for loop runs n times (where n is the length of the array).
The inner for loop runs 0, 1, 2, 3 … (n-1) for the worst case scenario wherein the array is in descending order.
Therefore the worst case scenario = > n(n-1)/2
At every inner for loop step a decision is made whether to swap. If we assume that at each step there is a 50% chance of swapping, then the average case scenario would be: (n(n-1)/2 ) / 2 approx.
The best case behavior would be visible when the array is already sorted => insertion sort would be linear in n.
Unlike insertion sort wherein the smaller element flows towards the beginning, here the larger element flows towards the end. Although the name might be catchy but it is not used industrially – there are other sorting algorithms that provide better perfomance.