Given an array of n elements, where each element is at most k away from its target position, devise an algorithm that sorts in O(n log k) time. For example, let us consider k is 2, an element at index 7 in the sorted array, can be at indexes 5, 6, 7, 8, 9 in the given array. I'm looking for code review, best practices, optimizations etc. Also for some reason I could not get assertarrayequals hooked up so tested arrays unconventionally. Please ignore that as part of feedback
public final class KSortedArray {
private KSortedArray() { }
/**
* Returns the sorted array provided the input array is k-sorted.
* If input array is not k-sorted, then results are unpredictable.
*
* @param arr The k-sorted array
* @param k the value of k, the deviation of placement.
* @return the sorted array
*/
public static int[] kSortDontModifyInput(int[] arr, int k) {
int[] n = new int[arr.length];
final Queue<Integer> queue = new PriorityQueue<Integer>(k + 1);
for (int i = 0; i <= k; i++) {
queue.add(arr[i]);
}
int ctr = 0;
for (int i = k + 1; i < arr.length; i++) {
n[ctr++] = queue.poll();
queue.add(arr[i]);
}
while (!queue.isEmpty()) {
n[ctr++] = queue.poll();
}
return n;
}
/**
* Sorted array provided the input array is k-sorted.
* If input array is not k-sorted, then results are unpredictable.
*
* @param arr The k-sorted array
* @param k the value of k, the deviation of placement.
*/
public static void kSortMoidifyInput(int[] arr, int k) {
Queue<Integer> queue = new PriorityQueue<Integer>(k + 1);
for (int i = 0; i <= k; i++) {
queue.add(arr[i]);
}
int ctr = 0;
for (int i = k + 1; i < arr.length; i++) {
arr[ctr++] = queue.poll();
queue.add(arr[i]);
}
while (!queue.isEmpty()) {
arr[ctr++] = queue.poll();
}
}
public static void main(String[] args) {
int arr[] = {2, 6, 3, 12, 56, 8};
int[] expected = {2, 3, 6, 8, 12, 56};
int[] actual = kSortDontModifyInput(arr, 3);
kSortMoidifyInput(arr, 3);
for (int i = 0; i < expected.length; i++) {
Assert.assertEquals(expected[i], actual[i]);
Assert.assertEquals(expected[i], arr[i]);
}
}
}