Sorting an almost sorted array (elements misplaced by no more than k)
algorithm, arrays, sorting
Solution
As Bob Sedgewick showed in his dissertation work (and follow-ons), insertion sort absolutely crushes the "almost-sorted array". In this case your asymptotics look good but if k < 12 I bet insertion sort wins every time. I don't know that there's a good explanation for why insertion sort does so well, but the place to look would be in one of Sedgewick's textbooks entitled Algorithms (he has done many editions for different languages).
I have no idea whether O(N log k) is optimal, but more to the point, I don't really care—if k is small, it's the constant factors that matter, and if k is large, you may as well just sort the array.
Insertion sort will nail this problem without re-sorting the same elements.
Big-O notation is all very well for algorithm class, but in the real world, constants matter. It's all too easy to lose sight of this. (And I say this as a professor who has taught Big-O notation!)
Problem
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?