Insertion Sort
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.