Given an array of n elements, where each element is at most k away from its target position, devise an algorithm that sorts in O(n log k) time.
For example, let us consider k is 2, an element at index 7 in the sorted array, can be at indexes 5, 6, 7, 8, 9 in the given array.
Actually we can easily utilize
Insertion Sort to sort it in O(nk) but it’s not ideal. Let’s try to use a small minHeap (of size k+1) to optimize it to O(nlogk).
Always welcome new ideas and
practical tricks, just leave them in the comments!