Решение задачи: отсортировать почти отсортированный массив

Я же не зря завел данную задачу, аккуратно после темы кучи (Heap). Как раз подобный вид сортировки - лучше сделать как раз при помощи Heap!

Алгоритм

1. Создайте минимальную кучу (min Heap) размера k + 1, с первыми элементами k + 1 (это кстати у вас займет где-то O(k)

2. Один за другим удалите минимальный элемент из кучи, помещая элемент в массив результатов и добавьте новый элемент в кучу из оставшихся элементов

Data Science: Алгоритмы и Структуры данных