Prove using INDUCTION:

procedure Countingsort$($arr$)$:

# Find the maximum and minimum values in the input

array

maxval$=$ 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