Sort a nearly sorted (or K 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.

Discussion :

- Create a Min Heap of size k+1 with first k+1 elements. This will take O(k) time 
- 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)

public void sortKSortedArray(List<Integer> list, int k){
    PriorityQueue<Integer> pq = new PriorityQueue<>(list.subList(0, k+1));
    for (int i = k + 1; i < list.size(); i++){
        System.out.print(pq.poll() + " ");
        pq.add(list.get(i));
    }
}