Interview Q: sorting an almost sorted array (elements misplaced by no more than k)

Question

I was asked this interview question recently:

You're given an array that is almost sorted, in that each of the N elements may be misplaced by no more than k positions from the correct sorted order. Find a space-and-time efficient algorithm to sort the array.

I have an O(N log k) solution as follows.

Let's denote arr[0..n) to mean the elements of the array from index 0 (inclusive) to N (exclusive).

• Sort arr[0..2k)
  • Now we know that arr[0..k) are in their final sorted positions...
  • ...but arr[k..2k) may still be misplaced by k!
• Sort arr[k..3k)
  • Now we know that arr[k..2k) are in their final sorted positions...
  • ...but arr[2k..3k) may still be misplaced by k
• Sort arr[2k..4k)
• ....
• Until you sort arr[ik..N), then you're done!
  • This final step may be cheaper than the other steps when you have less than 2k elements left

In each step, you sort at most 2k elements in O(k log k), putting at least k elements in their final sorted positions at the end of each step. There are O(N/k) steps, so the overall complexity is O(N log k).

My questions are:

• Is O(N log k) optimal? Can this be improved upon?
• Can you do this without (partially) re-sorting the same elements?

Answer 1

Since k is apparently supposed to be pretty small, an insertion sort is probably the most obvious and generally accepted algorithm.

In an insertion sort on random elements, you have to scan through N elements, and you have to move each one an average of N/2 positions, giving ~N*N/2 total operations. The "/2" constant is ignored in a big-O (or similar) characterization, giving O(N²) complexity.

In the case you're proposing, the expected number of operations is ~N*K/2 -- but since k is a constant, the whole k/2 term is ignored in a big-O characterization, so the overall complexity is O(N).

Answer 2

Your solution is a good one if k is large enough. There is no better solution in terms of time complexity; each element might be out of place by k places, which means you need to learn log2 k bits of information to place it correctly, which means you need to make log2 k comparisons at least--so it's got to be a complexity of at least O(N log k).

However, as others have pointed out, if k is small, the constant terms are going to kill you. Use something that's very fast per operation, like insertion sort, in that case.

If you really wanted to be optimal, you'd implement both methods, and switch from one to the other depending on k.

Answer 3

If using only the comparison model, O(n log k) is optimal. Consider the case when k = n.

To answer your other question, yes it is possible to do this without sorting, by using heaps.

Use a min-heap of 2k elements. Insert 2k elements first, then remove min, insert next element etc.

This guarantees O(n log k) time and O(k) space and heaps usually have small enough hidden constants.

Answer 4

I think you can use a quicksort-like method to get it down to K log N.

If you do a partition step but only consider elements within K of the pivot then you have the same guarantee as you do in quicksort.

1. the largest N/2 elements are in the top half of the array
2. the smallest N/2 elements are in the lower half of the array
3. the pivot element is greater than the elements in the lower half of the array and less than the elements in the upper part of the array.

This leads to K steps for log N levels.