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?