Suppose you have n data values in in array A. Declare an array called Count. Look at the value in A[i]. Count the number of items in A that are smaller than the value in A[i]. Assign that result to count[i]. Declare an output array Output. Assign Output[count[i]] = A[i]. Think about what the size of Output needs to be. Is it n or something else? Write a method to sort based on this strategy.

Pseudocode:

?count the Sort(A, Output[], k) // also declare an array called count[] for the n values in A are in the range of 0 to k declare the array for count[range from 0 --> k] for i = 0 --> k // Loop 1 count[i] = 0 for j = 1 --> n // Loop 2 // count[i] contains the count of elements == i count[A[j]] = count[A[j]] + 1 for i = 1 --> k // Loop 3 // count[i] now contains the numbers less than or equal to i, and assign the result to count[i] count[i] = count[i] + [count[i - 1] for j = n --> 1 // Loop 4 from n back to 1. Output [count[A[j]]] = A[j] // declare an output array named Output, and assign A[i] to Output[count[i] count[A[j]] = count[A[j]] - 1 // count[i] now contains the numbers less than or equal to i

QUESTION: Analyze the cost of the sort written above. What is the impact of random, ordered, or reverse ordered data using the Loops in the above statement?