#insertion sort

userNumber = [15,73,29,66,35,11,43,21]
print ("unsorted array ",userNumber)
for j in range(1,8):
    nextNum = userNumber[j]
    print("j = ",j,"userNumber[j] ",userNumber[j])
#insert userNumber[j] into the sorted sequence userNumber[1..j-1]
    print("Put userNumber(j) in the correct position .. remember array starts at 0")
    i = j - 1
    while i>=0 and userNumber[i]>nextNum:
       userNumber[i + 1] = userNumber[i]
       i = i - 1       
    userNumber[i + 1] = nextNum
    print("j = ",j, "array = ",userNumber)
print ("\nsorted array: ", userNumber)