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
    _______________ # 插入元素到正确位置