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

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:

1. We will create a min-heap which have a minimum value at its roots.
2. The size of the heap should be (k+1) as at any moment we store k+1 elements into the min-heap and remove root element and store it in array at the correct position with the help of some index variable.
3. At first, we store k+1 elements into the heap and initialize the index variable with 0 and the loop variable with the current index that is k.
4. At each iteration of the loop, we increment the index variable with +1 and loop variable with +1.
5. At last, when all iteration is completed with the loop we if we still have few elements left in the heap then we pop it and store it into the given array.

The overall time complexity for the above approach in the worst case is: O(nlog(k))

Space complexity for the above approach in worst case i: O(k+1)

C++ Implementation (Heap Approach):

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int main()
{
    cout << "Enter number of test cases: ";
    ll t;
    cin >> t;

    while (t--) {
        cout << "Enter N and K: ";
        ll n, k;
        cin >> n >> k;

        ll arr[n];

        cout << "Enter array elements: ";
        for (ll i = 0; i < n; i++)
            cin >> arr[i];

        //declare priority queue(min heap)
        priority_queue<ll, vector<ll>, greater<ll> > pq;

        //push k+1 first element of the array
        //into the priority queue.
        for (ll i = 0; i <= k; i++)
            pq.push(arr[i]);

        //declare index variable with 0.
        ll index = 0;

        //iterate through rest elements and
        //store k+1 elements into the heap.
        //during each iteration.
        for (ll i = k + 1; i < n; i++) {
            arr[index] = pq.top();
            pq.pop();
            pq.push(arr[i]);
            index++;
        }

        //store elements in correct position
        //till heap is empty.
        while (!pq.empty()) {
            arr[index] = pq.top();
            pq.pop();
            index++;
        }

        cout << "Final array: ";
        for (ll i = 0; i < n; i++)
            cout << arr[i] << " ";
        cout << "\n";
    }

    return 0;
}

Output:

Enter number of test cases: 3
Enter N and K: 4 2
Enter array elements: 3 1 2 4
Final array: 1 2 3 4 
Enter N and K: 10 2
Enter array elements: 1 4 5 2 3 7 8 6 10 9
Final array: 1 2 3 4 5 6 7 8 9 10 
Enter N and K: 6 4
Enter array elements: 4 3 2 1 5 6
Final array: 1 2 3 4 5 6