# Insertion sort Proof by Induction

I am reading Algorithm design manual by Skiena. It gives proof of Insertion sort by Induction. I am giving the proof described in the below.

Consider the correctness of insertion sort, which we introduced at the beginning of this chapter. The reason it is correct can be shown inductively:

1. The basis case consists of a single element, and by definition a one-element array is completely sorted.
2. In general, we can assume that the first n − 1 elements of array A are completely sorted after n − 1 iterations of insertion sort.
3. To insert one last element x to A, we find where it goes, namely the unique spot between the biggest element less than or equal to x and the smallest element greater than x. This is done by moving all the greater elements back by one position, creating room for x in the desired location.

I do not understand paragraph #3. Could someone please explain it to me with an example?

• Maybe this animation on Wikipedia's page on insertion sort will help you understand the 3rd point and the algorithm. Jun 2 '13 at 17:14
• one more thing, if you are beginner in Algorithms, then try book by Dasgupta or CLRS.
– avi
Jun 2 '13 at 18:52
• Looking at the proof without the algorithm (in exactly the same version the author uses) does not make much sense.
– Raphael
Jun 2 '13 at 22:50