Given an unsorted array. The array has this property that every element in array is at most k distance from its position in sorted array where k is a positive integer smaller than size of array. Which sorting algorithm can be easily modified for sorting this array and what is the obtainable time complexity?
A) Insertion Sort with time complexity O(kn)
B) Heap Sort with time complexity O(nLogk)
C) Quick Sort with time complexity O(kLogk)
D) Merge Sort with time complexity O(kLogk)
Answer given is B, and i somewhat get the resoning behind it,but one thing which i can not understand is why can't we follow same resoning even if this information that every element is distant by k units is not given?
The resoning is :
1) Create a Min Heap of size k+1 with first k+1 elements. This will take O(k) time (See this GFact)
2) One by one remove min element from heap, put it in result array, and add a new element to heap from remaining elements.
Removing an element and adding a new element to min heap will take Logk time. So overall complexity will be O(k) + O((n-k)*logK.
Pls provide your explantion