# Insertion sort
# Date: Tuesday, March 24, 2009

print 'Insertion sort\n'
print 'How many numbers would you like to enter: '
num = input()

print 'Please enter ' + str(num) + ' numbers'

numbers = []
for i in range(num):
    numbers += [input()]

for j in range(1, num):
    key = numbers[j]
    i = j-1
    # Keep shifting elements to the right until the right position is found
    while numbers[i] > key and i >= 0:
        numbers[i+1] = numbers[i]
        i = i - 1
    numbers[i+1] = key
    print(numbers)

Leave a Reply