algorithm:

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]$

$//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$

Your sort $()$ takes the array A $($input$)$ and value $k$ as arguments. In Java, determine $n$

by asking the array for its length.

Create public static method sort$()$ which implements a counting sort for non$-$negative integers. It takes two parameters:

an array of integers $($int$[]$ input$)$ containing the values to be sorted as the first argument $-$ do not change the contents of this array

an int maximumValue which is the largest value the input array may contain as the second argument

sort$()$ returns a new array of integers containing the sorted output.

Note: you will not be given any values outside the specified range $-$ do not check for negative or 'too large' values.