Search code examples
arraysalgorithmsortinginsertion-sortin-place

k messed sorted array using Insertion sort

In the familiar problem where every element in an array is at most k positions away from it's correct location, either to the left or to the right, I don't completely understand how the Insertion sort algorithm works.

I drew it on a paper, and debugged it step. It does seem to work, and the order of time complexity is O(n.k) as well.

But my question, is that, in this problem, the element could be k positions away either in the left or in the right. However, insertion sort only checks left. How does it still manage to get it right? Could you please explain to me, how this algorithm still works, although we look only to the left, in a manner I can convince myself?

PS : Irrelevant here : If I wasn't aware of this algorithm, I would've thought of something like Selection sort, where for a given element, i, you look k positions on the left and right, to choose the smallest element.

PS : Even more irrelavant : I'm aware of the min-heap based method for this. Again, the same question, why do we only look left?

Solution

  • Items to the left of the correct location get pushed right while the algorithm is processing smaller items. (Assuming that we're sorting in ascending order.) For example, if k is 3 and the initial array is 

    D A B E H C F G

    Let's examine how D gets to location 3 in the array. (Using zero-based indexing, D starts at index 0, and needs to move to index 3 in the array.)

    The first pass starts at E, and finds that it can swap A and D resulting in

    A D B E H C F G

    Second pass starts at H, and swaps B and D

    A B D E H C F G

    Third pass starts at C, and swaps C with H, E, and D

    A B C D E H F G

    And now you see that D is already where it's supposed to be.

    That's always going to be the case. Any element that starts to the left of its final position will be pushed right (to its final position) as smaller elements are processed. Otherwise, the smaller elements aren't in their correct locations. And an element (like D) won't get pushed past it's correct location, because the algorithm won't swap that element with elements that are larger.