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:
- The basis case consists of a single element, and by definition a one-element array is completely sorted.
- In general, we can assume that the first n − 1 elements of array A are completely sorted after n − 1 iterations of insertion sort.
- 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?