Write in C

Insertion sort

Assume that A$[$n$-2]$ elements are already sorted. All we need is to find an appropriate position for A$[$n $1]$ among the sorted elements and insert it there. This is usually done by scanning the sorted subarray from right to left until the first element smaller than or equal to A$[$n $1]$ is encountered to insert A$[$n $1]$ right after that element. The resulting algorithm is called straight insertion sort or simply insertion sort.

Though insertion sort is clearly based on a recursive idea, it is more efficient to implement this algorithm bottom up$,$ i$.$e$.,$ iteratively. Starting with A$[1]$and ending with A$[$n $1],$A$[$i$]$is inserted in its appropriate place among the first i elements of the array that have been already sorted $($but$,$ unlike selection sort, are generally not in their final positions$).$ Here is pseudocode of this algorithm.

$//$Sorts a given array by insertion sort

$//$Input: An array A$[0..$n $1]$ of integers given as command line arguements

$//$Output: Array A$[0..$n $1]$ sorted in nondecreasing order

ALGORITHM InsertionSort$($A$[0..$n $1])$

printArray

for i $1$ to n $1$ do

v $$ A$[$i$]$

j $$ i $1$

while j $>=0$ and A$[$j$]>$ v do

A$[$j $+1]$ A$[$j$]$

j $$ j $1$

A$[$j $+1]$ v

printArray

FIGURE $4\mathrm{.}3$ Iteration of insertion sort: A$[$i$]$ is inserted in its proper position among the preceding elements previously sorted.

$4\mathrm{.}1$ Insertion Sort

$89|456890293417$

$4589|6890293417$

$456889|90293417$

$45688990|293417$

$2945688990|3417$

$293445688990|17$

$17293445688990$

Example of sorting with insertion sort. A vertical bar separates the sorted part of the array from the remaining elements; the element being inserted is in bold.