In What kind of problems it is good to use counting sort, the worst case time complexity of it is : O(N + K), but if K is large it is not advisable to use counting sort. My question is that how do I know in what kind of problems I should use counting sort.
When is it ideal to use counting sort?
Hi raghav
It is kind of tradeoff when using counting sort
It runtime complexity : O(n+k) i.e. linear (when k is comparable to n) but space complexity is O(k)
Strengths:
- Linear time. Its asymptotically faster than comparison-based sorting algorithms like quicksort or merge sort.
Weaknesses:
- Counting sort can be used only to sort discrete values (for example integers), because otherwise the array of frequencies cannot be constructed.
- Restricted inputs. Counting sort only works when the range of potential items in the input is known ahead of time.
- Space cost. If the range of potential values is big, then counting sort requires a lot of space.
It is kind of less popular than the most common like quicksort due to more disadvantages. But if you get over the restrictions mentioned above you can use it get a very fast runtime.
Hope it helps
Mark resolved if satisfied 
I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.
On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.