def insertion_sort(arr):
    # starting from second index
    for i in range (1, len(arr)):
        key = arr[i]    # The element we want to insert
        j = i - 1       # Last house of sorted section

        # Shift it right until the left member is greater than key
        while j >= 0 and arr[j] > key:
            arr[j+1] = arr[j]
            j -= 1
        # Finally, put the key in the right place
        arr[j+1] = key




# Example:

nums = [5, 2, 4, 6, 1, 3]
print("Before sorting:", nums)

insertion_sort(nums)
print("After sorting:", nums)