Insertion sort is a simple sorting algorithm that builds the sorted array one item at a time.

Efficient for small data sets, not efficient for large data sets.

Most of the time we sort the playing cards in our hand using insertion sort without knowing about it.

At any given time, your array will be partially sorted and partially unsorted. At the end, you will have fully sorted array.

In every iteration, one element will be taken from unsorted array and placed at its right position in the sorted array. Iteration ends when there are no elements left in the unsorted array.

Pseudo Code:

i ← 1
while i < length(A)
j ← i
while j > 0 and A[j-1] > A[j]
swap A[j] and A[j-1]
j ← j - 1
end while
i ← i + 1
end while

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________