Prove the correctness of the below given algorithm.

procedure CountingSort$($arr$)$:

# Find the maximum and minimum values in the input

array

max$\_$val $=$ findMax $($arr$)$

min$\_$val $=$ findMin$($arr$)$

# Create an array to store the count of each element in

the input array

count $=$ array of size $($max$\_$val $-$ min$\_$val $+1)$

initialized with $0$

# Count the occurrences of each element in the input

array

for num in arr:

count$[$num $-$ min$\_$val$]+=1$

# Update the count array to store the cumulative count

for i from $1$ to length $($count$)-1$:

count$[$i$]+=$ count$[$i $1.$

# Create the output array

output $=$ array of size length$($arr$)$

# Build the output array using the count array

for num in reverse$($arr$)$:

output$[$count$[$num $-$ min$\_$val$]-1]=$ num

count $[$num $-$ min$\_$val$]-=1$

return output