We want to implement another sorting algorithm called insertion sort.

For doing that, we iterate over all elements

in the input array. As we examine each element, we perform a series of swaps to

move it to the place it belongs in the sorted left side of the array.

As example, consider the array $[2$; $4$; $5$; $3]($in math notation$)$:

We first consider the element $2$ at index $0.$ Since there is nothing to its left,

we don$$t need to do anything to sort the array up to this index.

Next we consider $4$ at index $1.$ The element to its left, $2,$ is smaller. If

we understand $[2]$ as a sorted array, then $4$ needs to remain to its right.

Therefore no swap is necessary.

Next we consider $5$ at index $2.$ The array $[2$; $4]$ to its left is sorted. Again

$5$ is larger than $4,$ so we don$$t need to perform any swap to make the array

$[2$; $4$; $5]$ sorted.

Finally, we consider $3$ at index $3.$ This element is smaller than $5$ to its

left. Therefore, we will need to perform at least one swap to place $3$ in its

sorted position. Thus, we swap $3$ with $5,$ obtaining the array $[2$; $4$; $3$; $5],$

where $3$ is larger than the element to its left, $2.$ Therefore we swap $3$ with $4,$

obtaining $[2$; $3$; $4$; $5].$ Now, $3$ is larger than $2,$ and therefore no further swaps

are needed.

Since we have gone through all the elements of the input array, the array we

obtained, $[2$; $3$; $4$; $5]$ is the final sorted array.

Draw pictures to figure out what portion of

the array is sorted at each point.

Express your findings as loop invariants using

functions in the array$\_$util library.

Implement the function in the docker in a new file insort.c$0$ by using the same interface of selsort.c$0($lab$3)$

Test and measure the time of the new sorting algorithm by using the main in sort$-$time.c$0($lab$3).$ What is the run time of this sorting algorithm?