def insertion_sort_optimized(arr):
    n = len(arr)
    for i in range(1, n):
        key = arr[i] # 当前待插入元素
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j] # 元素后移
            j -= 1
        _______________ # 插入元素到正确位置