def insertionSort(arr):
    n = len(arr)  # Get the length of the array
 
    if n <= 1:
        return  # If the array has 0 or 1 element, it is already sorted, so return
 
    for i in range(1, n):  # Iterate over the array starting from the second element
        key = arr[i]  # Store the current element as the key to be inserted in the right position
        j = i-1
        while j >= 0 and key < arr[j]:  # Move elements greater than key one position ahead
            arr[j+1] = arr[j]  # Shift elements to the right
            j -= 1
        arr[j+1] = key  # Insert the key in the correct position
 
# Sorting the array [12, 11, 13, 5, 6] using insertionSort
arr = [12, 11, 13, 5, 6]
insertionSort(arr)
print(arr)

ZGVmIGluc2VydGlvblNvcnQoYXJyKToKICAgIG4gPSBsZW4oYXJyKSAgIyBHZXQgdGhlIGxlbmd0aCBvZiB0aGUgYXJyYXkKICAgICAgCiAgICBpZiBuIDw9IDE6CiAgICAgICAgcmV0dXJuICAjIElmIHRoZSBhcnJheSBoYXMgMCBvciAxIGVsZW1lbnQsIGl0IGlzIGFscmVhZHkgc29ydGVkLCBzbyByZXR1cm4KIAogICAgZm9yIGkgaW4gcmFuZ2UoMSwgbik6ICAjIEl0ZXJhdGUgb3ZlciB0aGUgYXJyYXkgc3RhcnRpbmcgZnJvbSB0aGUgc2Vjb25kIGVsZW1lbnQKICAgICAgICBrZXkgPSBhcnJbaV0gICMgU3RvcmUgdGhlIGN1cnJlbnQgZWxlbWVudCBhcyB0aGUga2V5IHRvIGJlIGluc2VydGVkIGluIHRoZSByaWdodCBwb3NpdGlvbgogICAgICAgIGogPSBpLTEKICAgICAgICB3aGlsZSBqID49IDAgYW5kIGtleSA8IGFycltqXTogICMgTW92ZSBlbGVtZW50cyBncmVhdGVyIHRoYW4ga2V5IG9uZSBwb3NpdGlvbiBhaGVhZAogICAgICAgICAgICBhcnJbaisxXSA9IGFycltqXSAgIyBTaGlmdCBlbGVtZW50cyB0byB0aGUgcmlnaHQKICAgICAgICAgICAgaiAtPSAxCiAgICAgICAgYXJyW2orMV0gPSBrZXkgICMgSW5zZXJ0IHRoZSBrZXkgaW4gdGhlIGNvcnJlY3QgcG9zaXRpb24KICAKIyBTb3J0aW5nIHRoZSBhcnJheSBbMTIsIDExLCAxMywgNSwgNl0gdXNpbmcgaW5zZXJ0aW9uU29ydAphcnIgPSBbMTIsIDExLCAxMywgNSwgNl0KaW5zZXJ0aW9uU29ydChhcnIpCnByaW50KGFycik=