# Nearly Sorted

Moderate
0/80
Average time to solve is 10m
Contributed by

## Problem statement

Youâ€™re given an array/list 'ARR' of N elements, where each element is at most K away from its target position(Position if the array was sorted). Now, your task is to devise an algorithm that sorts the given array in O(N log K) time.

For example:

``````Let us consider 'K' is 3, an element at index 4 in the sorted array, can be at indexes 1, 2, 3, 4, 5, 6, 7 in the given array, because the absolute difference of all these indices with 4 is at most 3.
``````
Detailed explanation ( Input/output format, Notes, Images )
Constraints:
``````1 <= T <= 100
1 <= K < N <= 5000
1 <= ARR[i] <= 10^9

Time Limit: 1 sec
``````
##### Sample Input 1:
``````1
7 3
6 5 3 2 8 10 9
``````
##### Sample Output 1:
``````2 3 5 6 8 9 10
``````
##### Explanation For Sample Input 1:
``````We could move 6 from position 1 to as far as position 4 (as K=4) and we moved it to position 4 and it can be seen that after that all elements to the left(i.e position 1 to 3) are less than 6, hence 10 is at its best position now. Similarly, we do this for all the elements, to reach our answer.
``````
##### Sample Input 2:
``````1
8 4
10 9 8 7 4 70 60 50
``````
##### Sample Output 2:
``````4 7 8 9 10 50 60 70
``````
##### Explanation For Sample Input 2:
``````We could move 10 from position 1 to as far as position 5(as K=4) and we moved it to position 5 and it can be seen that after that all elements to the left(i.e position 1 to 4) are less than 10, hence 10 is at its best position now. Similarly we do this for all the elements, to reach our answer.
``````
Console