Задача: отсортировать почти отсортированный массив

Дан массив из n элементов, где каждый элемент находится не более чем на k от своей целевой позиции. Разработайте алгоритм, который выполняет сортировку за время O(n log k)

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