Q$-4)(10$ pts$.)$ 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 variable smaller than size of 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 sorting algorithm that uses a Min$-$Heap:

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

One by one remove min elements from heap, put it in result array, and

add a new element to heap from remaining elements.

Provide a tight asymptotic upper bound for this algorithm. Explain briefly.