Insertion sort proof 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 cannot understand the last pragraph(i.e 3).Could someone please explain me with an example?
 A: Assuming it is sorting in increasing order: so by induction the first $n-1$ elements of $A$ are sorted, so one example you can think of is $[1,2,3,4,6,7,8,9,5]$. It needs to insert that last element somewhere in $A$ and ensure all of $A$ will be sorted. So it will look for an index $k$, such that $a_k \leq x < a_{k+1}$, and then insert $x$ between elements $k$ and $k+1$. Because the rest of $A$ is sorted, this index $k$ will be unique, and once $x$ is inserted, the whole of $A$ will now be sorted. The bit about moving elements by one position just describes how it inserts $x$ into $A$. Does this help?
A: The algorithm will have the property that at each iteration, the array will consist of two subarrays: the left subarray will always be sorted, so at each iteration our array will look like
$$
\langle\; \text{(a sorted array)}, \fbox{current element},\text{(the other elements)}\;\rangle 
$$
We work from left to right, inserting each current element where it belongs in the sorted subarray. To do that, we find where the current element belongs, shift the larger elements one position to the right, and place the current element where it belongs.
Consider, for example, the initial array $\langle\; 7, 2, 6, 11, 4, 8, 5\;\rangle$. We start with
$$
\langle\; \fbox{7}, 2, 6, 11, 4, 8, 5\;\rangle
$$
The sorted part is initially empty, so inserting the 7 into an empty array will just give the array $\langle\;7\;\rangle$.
In the second iteration we have
$$
\langle\; 7, \fbox{2}, 6, 11, 4, 8, 5\;\rangle
$$
and now your part (3) comes into play: we find that the element 2 belongs at the front of the sorted list, so we shift the 7 one position to the right and insert the 2 in its proper location, giving us
$$
\langle\; 2, 7, \fbox{6}, 11, 4, 8, 5\;\rangle
$$
Inserting the 6 in its proper place (after shifting the 7 to make room) in the sorted subarray yields
$$
\langle\; 2, 6, 7, \fbox{11}, 4, 8, 5\;\rangle
$$
Continuing this process, we'll have
$$
\langle\; 2, 6, 7, 11, \fbox{4}, 8, 5\;\rangle
$$
(since the 11 is already where it should be, so no shifting was necessary). Then we have
$$
\langle\; 2, 4, 6, 7, 11, \fbox{8}, 5\;\rangle
$$
(shifting the 7 and 11). Then
$$
\langle\; 2, 4, 6, 7, 8, 11, \fbox{5}\;\rangle
$$
and, finally, we use paragraph (3) one final time to get
$$
\langle\; 2, 4, 5, 6, 7, 8, 11\;\rangle
$$
