Цикл while использует линейный поиск для сканирования в обратном направлении. Однако мы знаем, что массив в цикле while уже отсортирован. Таким образом, мы можем заменить линейный поиск на бинарный поиск, так что O (n) изменится на O (lg n). Тем не менее, я считаю, что это не будет способствовать сокращению общего времени, потому что нам все равно придется перемещать элементы на один индекс вперед, что всегда будет проходить (количество шагов назад (n)) раз. Таким образом, в целом время выполнения остается O (n ^ 2), и нет никакого способа достичь O (n lg n) для этого случая. Пожалуйста, скажите мне, если я подхожу к этому неправильно.

INSERTION-SORT(A)

 for j = 2 to length[A]
  do key = A[j]
     i = j - 1

  while i > 0 and A[i] > key
    A[i+1] = A[i]
    i = i - 1

  A[i+1] = key