Сортировка почти отсортированного массива со сложностью O (n * Log (K))

Question

Задача -Последний отсортированный массив- Учитывая массив из n элементов, каждый из которых находится на расстоянии не более K Позиции от своей фактической позиции в отсортированном массиве, разработайте алгоритм, который сортирует по времени O (nLogK).

Approach - I divide the array in n/K elements each(n/k + 1 , if n%k!=0).

Then I run a loop n/k times ,inside which I sort eack n/k group using 
MergeSort(Complexity = KLogK).So complexity for the loop is O(nLogK).

Finally I merge the n/k groups using a Merge Function(similar to Merging 
K Sorted arrays, complexity = nLog(n/k)).

So overall complexity is between nLogK and nLog(n/K) but I have to 
achieve complexity O(nLogK).
Comparing K and n/K depends on values of n and K.

Может ли кто-нибудь помочь мне с последней операцией слияния или с лучшим подходом.

PS: я не знаю кучи или очереди в то время, поэтому я ищу решение, которое не включает их.

Answer 1

Сначала разделите массив на группы по крайней мере k+1 элементов. Таким образом, правильная позиция каждого элемента находится либо внутри группы, в которой элемент находится в данный момент, либо внутри группы слева или справа, но не дальше. Затем отсортируйте каждую группу.

Этот шаг занимает O((n/k) * k log k) = O(n log k).

Затем, после сортировки каждой группы, вы можете объединить i группу с группой i+1, для i с 1 до n/(k+1) - 1.

Под слиянием я понимаю процедуру слияния из сортировки слиянием. Группы не объединяются. Их размеры остаются прежними.

Каждое слияние занимает O(n/k), всего этот шаг O(n).