[Math] Insertion sort proof

algorithms

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 cannot understand the last pragraph(i.e 3).Could someone please explain me with an example?

Best Answer

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?

Related Question