title: Sorting an almost sorted array (elements misplaced by no more than k)
body: <p>I was asked this interview question recently:</p>
  
  <blockquote>
    <p>You're given an array that is almost sorted, in that each of the <code>N</code> elements may be misplaced by no more than <code>k</code> positions from the correct sorted order. Find a space-and-time efficient algorithm to sort the array.</p>
  </blockquote>
  
  <p>I have an <code>O(N log k)</code> solution as follows.</p>
  
  <p>Let's denote <code>arr[0..n)</code> to mean the elements of the array from index <code>0</code> (inclusive) to <code>N</code> (exclusive).</p>
  
  <ul>
  <li>Sort <code>arr[0..2k)</code>
  
  <ul>
  <li>Now we know that <code>arr[0..k)</code> are in their final sorted positions...</li>
  <li>...but <code>arr[k..2k)</code> may still be misplaced by <code>k</code>!</li>
  </ul></li>
  <li>Sort <code>arr[k..3k)</code>
  
  <ul>
  <li>Now we know that <code>arr[k..2k)</code> are in their final sorted positions...</li>
  <li>...but <code>arr[2k..3k)</code> may still be misplaced by <code>k</code></li>
  </ul></li>
  <li>Sort <code>arr[2k..4k)</code></li>
  <li>....</li>
  <li>Until you sort <code>arr[ik..N)</code>, then you're done!
  
  <ul>
  <li>This final step may be cheaper than the other steps when you have less than <code>2k</code> elements left</li>
  </ul></li>
  </ul>
  
  <p>In each step, you sort at most <code>2k</code> elements in <code>O(k log k)</code>, putting at least <code>k</code> elements in their final sorted positions at the end of each step. There are <code>O(N/k)</code> steps, so the overall complexity is <code>O(N log k)</code>.</p>
  
  <p>My questions are:</p>
  
  <ul>
  <li>Is <code>O(N log k)</code> optimal? Can this be improved upon?</li>
  <li>Can you do this without (partially) re-sorting the same elements?</li>
  </ul>