algorithm - 对具有 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)。