Given an unsorted array, the array has this property that every element in the array is at most k distance from its position in a sorted array where k is a positive integer smaller than the size of the array. 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. We can sort such arrays more efficiently with the help of Heap data structure. Following is the algorithm that uses a Heap.

- Create a Min Heap of size k+1 with the first k+1 elements.

- One by one remove min element from the heap, put it in the result array, and add a new element to the heap from the remaining elements.

Provide a tight asymptotic upper bound for this algorithm. Show your work.