K Messed Array sort in Java
You should add a bounds check that k is not larger than your array, because I don't see that explicitly mentioned in the problem statement.

for( int i = 0; i &lt;= k; i++ )
   queue.add(arr[i]);


I think you should always add braces, but that's my personal opinion.

//Store the first k+1 elements in the heap
for( int i = 0; i &lt;= k; i++ )
   queue.add(arr[i]);

for( int i = k+1; i &lt; arrLen; i++ )
{
  //Extract the minimum element in the priority queue
  arr[i - (k + 1)] = queue.poll();

  //Add the next element to the queue
  queue.add(arr[i]);
}


This bit would make more sense if you kept i as your arr index. Then swap the statement to get rid of the +1, ...

//Store the first k+1 elements in the heap
int i = 0;
for(; i &lt; k; i++ )
   queue.add(arr[i]);

for( ; i &lt; arrLen; i++ )
{
  //Add the next element to the queue
  queue.add(arr[i]);

  //Extract the minimum element in the priority queue
  arr[i - k] = queue.poll();
}


This also makes the next section pretty readable;

for( i -= k; i &lt; arrLen; i++ ) //convert i into sorted array index by removing the k offset
  arr[i] = queue.poll();


You should also initialize the PriorityQueue with the capacity you're going to need; that's k + 1.