Motivation

Counting Sort never compares two elements. It uses their values directly as indices into a count array, which is what lets it run in linear time.

Why learn Counting Sort?

• Linear time: it runs in O(n + k), where n is the number of elements and k is the range of values. When k is small, that beats O(n log n).
• Stable (when done carefully): a foundation for Radix Sort, which chains several counting-sort passes.
• A different idea: sorting by tallying values rather than comparing them.

The trade-off: it needs O(k) memory for the count array, so it is a poor fit when the value range is huge (for example, sorting a handful of numbers up to a billion).