# Produce a nearly sorted (or K sorted) array

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++) {
}

int ctr = 0;
for (int i = k + 1; i < arr.length; i++) {
n[ctr++] = queue.poll();
}
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++) {
}
int ctr = 0;
for (int i = k + 1; i < arr.length; i++) {
arr[ctr++] = queue.poll();
}

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]);
}
}
}


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 < data.length; i++) {
int from = i > k ? i - k : 0;
int val = data[i];
int pos = Arrays.binarySearch(data, from, i, val);
if (pos < 0) {
pos = -pos - 1;
}
System.arraycopy(data, pos, data, pos+1, i - pos - 1);
data[pos] = val;
}

• I am a little consfused with your comment "which has O( log(n) ) time-complexity for add()", my question is why logn rather than logk if I have declared by Queue of size "k + 1" ? Feb 21, 2014 at 8:36
• Also I poll before I add another, once size exceeds k + 1. This means my queue is never more than k elements Feb 21, 2014 at 8:37
• @JavaDeveloper You are correct ... and, that goes to show why comments are important. Feb 21, 2014 at 11:27
• confused of how you use binary search when stuff in range is not sorted ? Mar 27, 2014 at 7:09
• The binary search is happening on the data that we are inserting in to. This is data that we are inserting 'in order'. We can guarantee that the last 'k' elements of that data are sorted, thus BSearch is fine. Mar 27, 2014 at 11:13

kSortDontModifyInput() and kSortMoidifyInput() use the same algorithm to do the sorting. The only difference is that kSortDontModifyInput() creates a new array instead of using the given one. Therefor you can implment kSortDontMoidifyInput() by making a copy of the input array and passing it to kSortMoidifyInput(). Since they are meant to be doing the same operation, if you find a bug in one, you don't have to remember to change the other one.