Sort Nearly Sorted Array
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.
Follow up: What if you don't know the size k?
Solution: Using Min Heap
- Create a Min Heap of size k+1 with first k+1 elements.
- Building heap will take O(k) time.
- One by one remove min element from heap, put it in result array
- Add a new element to heap from remaining elements.