Counting sort is an integer-based linear time sorting algorithm.
Where counting sort fails is if the input array is sparse. It functions best when the elements of are close to each other. Otherwise, we have a significant scaling factor on our space complexity .
See also
- Radix sort, the other main sorting algorithm