#### 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).