Consider the following two variants of the pseudo code for the Insertion Sort algorithm. Using each variant, sort the array: $5_1,5_2,5_3{5}_4,5_5.$ Note that $5_1,5_2,$dots,$5_5$ are five different instants of integer $5$ and need to be treated as separate elements $($that are of the same numerical value$).$ Determine the number of comparisons encountered with each of the two variants of the algorithm to sort the above array and what is the final sorted array $($include the suffixes of the elements throughout your work$).$

Input: Array A$[0..$n$-1]$

Begin

for $($index $i=1$ to $n-1)$ do

$v=A[i]$

index $j=i-1$

while $($index $j0)$ do

if $)(A[j]$ then

break $\text{'}j\text{'}$ loop

else

end if

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

$j=j-1$

end while

$A[j+1]=v$

End

Input: Array $A[0$dotsn$-1]$ Begin for $($index $i=1$ to $n-1)$ do $,v=A[i]$ index $j=i-1$ while $($index $j0)$ do

if $)>(A[j]$ then

break $\text{'}j\text{'}$ loop

else

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

end if

$j=j-1$

end while

$A[j+1]=v$

End

Pseudo Code $-$ I

Pseudo Code $-$ II