In this assignment you are asked to implement Counting Sort. This algorithm takes as input

an array of $n$ integers in the range of $0$ to $k.$ Its running time is $O(n),$ and hence is more

efficient than all algorithms seen in class. In contrast to those seen in class, Counting Sort

does not use comparisons.

The signature of the main class should be public class countingSort and is supposed to

contain the following method:

public static void sort$($int$[]$ A$)$

Next we present the pseudocode for counting$\_$SORT $($A$,$ B$,$ k$),$ taken from $[?].$ A is the array

$A[1..n]$ to be sorted and has length $n.$ Also, its elements are integers in the range $0..k.$ B is an

array $B[1..n]$ that will hold the sorted output. $c$ is an auxiliary array $c[0..k]$ for temporary

storage. You should use this as the basis for your Java implementation. Once you have

implemented it$,$ include some test cases.

Here is an example of a run. The array to be sorted is A whose size is $n=8.$

The integers in A are in the range $0$ to $k=5.$ Here is a trace:

At line $5$ :

At line $8$ :

Iteration $1$ of loop in line $9$:

Iteration $2$ of loop in line $9$ :

Iteration $3$ of loop in line $9$:

After all iterations of loop in line $9$: