Сортировка вставками

Пусть на $k$-ом шаге у нас уже отсортирован префикс длины $k$. Чтобы увеличить этот отсортированный префикс, мы можем взять элемент, следующий после него, и менять его с левым соседом, пока этот элемент не окажется больше своего левого соседа. Когда это произойдет, это будет означать, что он будет больше всех элементов слева и меньше всех элементов префикса справа, и значит мы правильно вставили этот элемент в отсортированную часть массива.

void insertion_sort(int *a, int n) {
    for (int k = 1; k < n; k++)
        for (int i = k; i > 0 && a[i - 1] < a[i]; i--)
            // мы ещё не дошли до начала массива и предыдущий элемент меньше
            swap(a[i], a[i - 1]);
}

Время работы в худшем случае тоже квадратичное — например, когда массив упорядочен по убыванию.

Однако, в отличие от двух предыдущих квадратичных сортировок, в некоторых хороших случаях время работы может быть меньше, потому что мы добавили условие ранней остановки во внутреннем цикле. Например, алгоритм сделает $O(n)$ операций, если массив изначально отсортирован.

Упражнение. Покажите, что алгоритм делает $O(n k)$ операций, если массив «почти отсортирован» в том смысле, что каждый элемент находится на расстоянии не более $k$ от его позиции в отсортированном массиве.