Answer: Insertion Sort Algorithm:-
This algorithm scans an array 'list' (with n element list, list , .... list[n]) from list  to list[n], inserting each element list [i] into its proper position in the previously sorted subarray list, list,......,list [i-1]. That is:
Pass 1: list  by itself is trivially sorted.
Pass 2: list  is inserted before or after list so that: list, list is sorted.
Pass 3: list  is inserted into its proper place in the list, list, that is before list, between list and list, or after list, so that: list, list, list, list is sorted.
Pass 4: list is inserted into its proper place in list, list, list, so that: list, lis, list, list, is sorted.
Pass n: list [n] is inserted into its proper place in list, list, ..., list[n-1] so that: list, list,... list[n-1], is sorted.
This algorithm is frequently using when n is small.
The problem of deciding how to insert list[i] in its proper place in the sorted subarray list, list,...,list[i-1], can be accomplished by comparing list[i] with list [i-j], comparing list[i] with [i-2], and so on, until first meeting an element list[j] such that list[j] <= list[i].
Then each of the element list[i-1], list[i -2], ..., list[j +1] is moved forward one location, and list[i] is then inserted in the j+1st position in the array. The algorithm is simplified if there always is an element list[j] such that list[j] <= list[i], otherwise, we must constantly check to see if we are comparing list[i] with list. This condition can by accomplished by using a sentinel element list = -∞ (or a very small number).
The insertion sort algorithm is given below:
Algorithm: (Insertion sort) INSERTION (list, n)
This algorithm sorts the array list with n elements;
Step 1: set list: =-∞ [Initialises sentinel element]
Step 2: Repeat Step 3 to 5 for i = 1,2,... n
Step 3: set temp: - list[i], and, ptr: = i - 1
Step 4: Repeat while temp < list[ptr]
(a) set list[ptr + 1]: = list[ptr] [moves element forward]
(b) set ptr: = ptr -1 [End of loop]
Step 5: set list[ptr + 1]: = temp [Inserts element in proper place] [End of Step 2 loop]
Step 6: Return
Complexity of Insertion Sort:
The worst case occurs when the array 'list' is in reverse order and inner loop must use the maximum number i-1 of comparisons.
Hence, total comparisons are :
f(n) = 1 + 2 + 3 +.....+ (n - 1) =n(n-1)/2=O(n2)
In the average case there will be approximately (i - 1)/2 comparisons in the inner loop.
Thus, it is a very slow algorithm when n is very large.