Produce a nearly sorted (or K sorted) array
When you use a class in a 'hacky' way, like you do by using a PriorityQueue as a TreeSet, you should make sure that you document why the class is used, and what properties of the class are being leveraged.


Your code does not work in O(n log(k) ) time because it uses a PriorityQueue, which has O( log(n) ) time-complexity for add():


  Implementation note: this implementation provides O(log(n)) time for the enqueing and dequeing methods (offer, poll, remove() and add); linear time for the remove(Object) and contains(Object) methods; and constant time for the retrieval methods (peek, element, and size)




Your algorithm is not correct for the requirements given:


For a start, it will fail for input where the input array is smaller than k. It will throw an ArrayIndexOutOfBoundsException.
Secondly, you are working in k+1 space instead of k. Why? Where is the comment?


Further, because you auto-box all your values to Integer, from int, you have a significant performance penalty. If you keep your data as primitives (and use an array of primitives rather than a PriorityQueue), you will have better results.

The algorithm you need you use is strongly hinted at by the complexity requirement...

O( n log(k) ) strongly implies that you need to iterate over each value once, and, with that element, there is an O(log(k)) way to sort it.

For the loop, think a for-loop. For the log(k), think a binary search....

for (int i = 0; i &lt; data.length; i++) {
    int from = i &gt; k ? i - k : 0;
    int val = data[i];
    int pos = Arrays.binarySearch(data, from, i, val);
    if (pos &lt; 0) {
        pos = -pos - 1;
    }
    System.arraycopy(data, pos, data, pos+1, i - pos - 1);
    data[pos] = val;
}