Сортировать K-сортированный двусвязный список | Набор 2 (с использованием сортировки Шелла)

Для данного двусвязного списка, содержащего N узлов, где каждый узел находится не более чем на K от своей целевой позиции в списке, задача состоит в том, чтобы отсортировать данный двусвязный список.

Примеры:

Input: DLL: 3<->6<->2<->12<->56<->8, K = 2
Output: 
2<->3<->6<->8<->12<->56

Input: DLL: 3<->2<->1<->5<->4
Output:
1<->2<->3<->4<->5

Примечание. Здесь обсуждались подходы, использующие сортировку вставками и структуру данных минимальной кучи.

Подход: сортировка Шелла, которая является разновидностью сортировки вставками, также может быть использована для решения этой проблемы путем инициализации промежутка с помощью K вместо N, поскольку список уже отсортирован по K.

Ниже приведена реализация описанного выше подхода:

Временная сложность: O (N * log K)
gap инициализируется значением k и уменьшается до максимального значения gap/2 после каждой итерации. Следовательно, будет рассчитано log k пробелов, и для каждого пробела список будет повторяться.

Космическая сложность: O(1)