Does counting sort range always need to be in [0,k]?

Can I do a counting sort on a small range of numbers say A=[7,9,12,15] from a huge pool of numbers, which I know will consist of only the numbers in the small array? Or does the small range always have to be [0..开发者_如何学Ck].

I can do counting sort on the array A by saying [0..15] but it does not make sense. And what if A=[100,750,452]

So I guess it is feasible. I would like some inputs please.

Your question isn't very clear, but here it goes. From your example A=[7,9,12,15] the range be [0..15] and would require addition space of size k=15 (and another result array of A[length]. Since n (A[length]) is 4, the overall runtime would be theta(k + n). Counting sort is a "space-time tradeoff" algo, but if used in your case it wouldn't make any sense. Since, there isn't any tradeoff. Counting sort should be use when you have k=Big-O(n), which means the maximum value in your A[] is less than the size of A[]. btw, I believe the algorithm would still sort your example correctly.