COUNTING$-$SORT $(A,n,k)$

let $B[1$:$n]$ and $C[0$:$k]$ be new arrays

for $i=0$ to $k$

$C[i]=0$

for $j=1$ to $n$

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

$//C[i]$ now contains the number of elements equal to $i.$

for $i=1$ to $k$

$C[i]=C[i]+C[i-1]$

$\frac{\frac{?}{?}}{C}[i]$ now contains the number of elements less than or equal to $i.$

$//$ Copy $A$ to $B,$ starting from the end of $A.$

for $j=n$ downto $1$

$B[C[A[j]]]=A[j]$

$C[A[j]]=C[A[j]]-1\frac{,}{\frac{?}{?}}$ to handle duplicate values

return $B$

a$.$ Following the algorithm above, illustrate the operation of COUNTING$-$SORT on the array $A=$

$|$~$0,5,1,3,1$~$|$ by assuming $k=5.$ Show all intermediate steps, including changes on array B and C$.$

b$.$ Does the algorithm perform sorting in place? Justify your answer.

c$.$ Is the algorithm stable? Justify your answer.