以 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)。

然后，在对每个组进行排序后，您可以将ith 组与该i+1组合并，对于ifrom1到n/(k+1) - 1。

通过合并，我了解合并排序的合并过程。团体不团结。它们的大小保持不变。

每次合并需要O(n/k)，这一步总共是O(n)。