Question

A is an array with n elements such that each element is at most in k position away of its ordered position. Give an algorithm that sorts the elements of A on O(n log k).
Example: [2,1,4,3]

Answer 1

Algorithm to sort the elements of A where each element is at most in k position away of its ordered position.
Sort(A[],n,k)
inputs:A //array
n//legnth of A
k//distance k is less than n
now
heap = create a min heap with first k+1 elements in A//take O(klogk) time
now
index=0
for i=k+1 to n-1 ://runs n-k times
{
   A[index++] = heap.pop();//poping min element from heap and storing in sorted order :O(logk)
   heap.push(A[k+1]);//push new element :O(logk)
}//total complexity : O(nlogk)
//now pop all remaining elements from min heap
while(!heap.empty())//runs k times
{
   A[index++] = heap.pop();
}
//now array is sorted

Total complexity of algorithm : klogk+nlogk+k = O(nlogk)