Write a program of the Insertion Sort algorithm which sorts a sequence A in ascending order. The algorithm should be based on the following pseudocode:                 for i = 1 to A.length-1     key = A[i]     /* insert A[i] into the sorted sequence A[0,...,j-1] */     j = i - 1     while j >= 0 and A[j] > key         A[j+1] = A[j]         j--     A[j+1] = key   Note that, indices for array elements are based on 0-origin.  To illustrate the algorithms, your program should trace intermediate result for each step.
def main():
    N = int(input())
    A = list(map(int,input().split()))
    insertionSort(A, N)

def insertionSort(A, N):
    for i in range(1,N):
        v = A[i]
        j = i - 1
        while j>= 0 and A[j] > v:
            A[j+1] = A[j]
            j -= 1
        A[j+1] = v
        print(*A)

if __name__ == '__main__':
    main()

def main():
    N = int(input())
    A = list(map(int,input().split()))
    insertionSort(A, N)

def insertionSort(A, N):
    print(*A)
    for i in range(1,N):
        v = A[i]
        j = i - 1
        while j>= 0 and A[j] > v:
            A[j+1] = A[j]
            j -= 1
        A[j+1] = v
        print(*A)

if __name__ == '__main__':
    main()
