Insertion Sort

Has a quadratic order of growth and is therefore suitable for sorting small lists only.
Is much more efficient than bubble sort, if the list that needs to be sorted is nearly sorted.

Algorithm for insertion sort:

1.	Repeat steps 2, 3, 4, and 5 varying i from 1 to  n – 1.
2.	Set temp = arr[i].
3.	Set j = i – 1.
4. Repeat until j becomes less than 0 or arr[j] becomes 
  less than or equal to temp:
a. Shift the value at index j to index j + 1.
b. Decrement j by 1.
5.	Store temp at index j + 1.

Determining the Efficiency of the Insertion Sort Algorithm

To sort a list of size n by using insertion sort, you need to perform (n – 1) passes.
In n – 1 passes, you need to make n – 1 comparisons. This is the best case for insertion sort.
Therefore, the best case efficiency of insertion sort is of the order, O(n).
If the list is stored in the reverse order, you need to make n – 1 comparisons in the (n – 1)th pass.
The formula for determining the total number of comparisons in this case is:

Sum = 1 + 2 + . . . + (n – 1)

Therefore, the worst case efficiency of insertion sort is same as that of bubble sort, that is, O(n2).