Problem -Nearly Sorted Array- Given an array of n elements , each of which is atmost K Position away from it's actual position in the sorted array , devise an algorithm that sorts in O(nLogK) time.
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.
Can anyone help me with the final merging operation or a better approach.
PS : I do not know heaps or queues at the time so I am looking for a solution which does not involve these.