Insertion Sort:

Here the array is virtually divided in two parts: 1st part is Sorted and the 2nd one is Unsorted. It works as follows:

• Start with the 2nd element i.e A[1]. Store it in a variable called 'Value' and its index in 'hole'.
• Now while its previous element i.e. A[hole -1] is greater than the current element i.e.Value, copy the previous element in the current hole and reduce hole by 1.
• Once the condition breaks, put the value in A[hole]

def insertionSort(A):    
    for i in range(1,len(A)):
        value = A[i]
        hole = i
        while (hole>0 and A[hole-1]>value):
            A[hole] = A[hole-1]
            hole = hole-1
        A[hole] = value
    return A