# Sort K-Sorted Array

You are given an array of *n* elements such that each element is at max *k* place away from its original sorted position, you have to sort the array in the correct manner.

**Problem description:**

The problem asks you to sort the array in minimum possible time, the main catch here is how to use the information that the elements are at maximum k place away from its original sorted position.

**Input:**

The first line of the input consists of *T* number of test cases, each test case consists of *N* size of the array following line consist of *N* numbers as the input of the array.

**Output:**

You are required to print the sorted form of the array.

**Examples:**

Input:
T=1
N=4 2
3 1 2 4
Output:
1 2 3 4
Since 3 original position is at index 0
but in the sorted array it should be at index 2, 1 should be
at index 0 and 2 should bet at index 1 therefore maximum distance
between the current position and sorted position is 2
therefore it can be solved with the help of heap.
Input:
T=1
N=6 K=4
4 3 2 1 5 6
Output:
1 2 3 4 5 6
Similarly, as the previous case the maximum difference between
original index and current position is 3 for element 4 indexed at 0.

The problem asks you to solve it in an efficient manner since it is possible to sort the array with the help of insertion sort method which will take O(n*k) time since we have a total of a number of elements and each element can be at max k place away from its original position. So to avoid that time complexity we will use the heap data structure:

(k+1)as at any moment we storek+1elements into the min-heap and remove root element and store it in array at the correct position with the help of some index variable.k+1elements into the heap and initialize the index variable with 0 and the loop variable with the current index that isk.The overall

time complexityfor the above approach in the worst case is:O(nlog(k))Space complexityfor the above approach in worst casei:O(k+1)C++ Implementation (Heap Approach):

need an explanation for this answer? contact us directly to get an explanation for this answerOutput: