# We consider that there is a temporary sorted sublist starting
# with the first element and expanding on every pass. We start
# from arr[0..1], swapping the last element until it is in the
# proper position. Then we consider arr[0..2], arr[0..3] and so
# on until we reach arr[0..(n-1)], at which point the entire
# array is sorted

def insertionSort(arr):
    for i in range(1, len(arr)):
        for j in range(i, 0, -1):
            if arr[j] < arr[j - 1]:
                arr[j], arr[j - 1] = arr[j - 1], arr[j]


arr = [2, -4, -13, 6, 14, 16, -9, -5, 1, 7]
insertionSort(arr)
print(arr)