Please Show Work on how you are getting the results, the work leading up

Description Suppose you're sorting an array of n numbers. In class we investigated the runtimes of a variety of sorts. The simpler sorts had average runtimes of O(n). On the other hand, the more clever sorts had an average runtime of O(n log n) (i.e., merge sort and quicksort). Can sort faster than O(n log n)? To explore that idea let's implement a slightly strange sorting idea: Algorithm 1 void counting Sort(int A[], int k) 1: //Precondition: A contains n values which are all between 0 and k 2: Let C be a new array of k +1 elements 3: Let B be a new array of n elements 4: for i=0 to k do 5: C[i] = 0; 6: end for 7: for i=1 to n - 1 do CA[i] + +; 9: end for 10: //C[i] now contains the # of elements in A equal to i 11: for i=1 to k do 12: C[i] = C[i] + C[i 1]; 13: end for 14: //C[i] now contains the # of elements in A that are