Counting Sort is a non-comparison sorting algorithm. Instead of comparing elements against each other, it counts how many times each value appears, then uses those counts to place every element directly into its correct position in the output array.
This makes it exceptionally fast when the range of values (k) is small relative to the number of elements (n). There are no swaps, no comparisons — just counting and placing.
Never compares two elements — it counts occurrences. This breaks the O(n log n) lower bound for comparison sorts.
Linear in the number of elements plus the value range. Faster than any comparison sort when k is small.
Requires values to be non-negative integers within a known range — not suitable for floats or arbitrary objects.
TIPCounting Sort shines when sorting integers in a small range — e.g. ages, grades, or frequencies. For large ranges or floating point values, use a comparison sort instead.