Написать алгоритм со временем выполнения O(n)

Есть вот такое задание

Массив А[1, …, n] будет называться d-отсортированным (для d ≤ n) если каждый ключ в массиве находиться на расстоянии не более чем d от его места в массиве А в котором он будет отсортирован. Нужно сделать алгоритм который сортирует d-отсортированным массив размером n и сортирует его.

и вот такой вопрос

напишите алгоритм у которого время выполнения в самом плохом случае O(n) если d постоянная.

Какой это может быть алгоритм?