DEV Community


Discussion on: Counting Linearly With Counting Sort

vandanav profile image

I really love the way you break down complex concepts into simpler ones with a wild real-world mapping.

However this counting sort is kinda confusing in the sense I've read some resources that say one can apply counting sort only if 'k'(the highest no. in the array) is less than 'n'(the total no. of elements in the array). And even you have mentioned it while explaining its space complexity. However, in your example the highest is 9 and the no. of array elements is 8. Yet we proceeded with counting sort. Is it due to some other governing factor? And why do we have to shift the elements in our count array?

I would love to wrap my head around this concept. Could you please help me out with this?