Counting Sort

Spotting one

The values are numbers in a small, known range. Ages, scores, letters, ratings. And there are many more items than there are distinct values.

Or the question is about how often things appear, which is the same machinery seen from another angle.

The idea, plainly

Do not compare anything. Count how many times each value appears, then walk the counts in order and write each value out that many times.

Because it never compares two items, it escapes the speed limit that applies to every sorting method built on comparisons. The price is that it only works while the range of values stays small enough to count across.

Where to start

Relative Sort Array first. It is counting sort with a custom order laid over the top, and the values are small by design.

Minimum Absolute Difference shows the pattern without ever mentioning sorting. Once values are in order the closest pair has to be neighbours, so you only compare each item with the next one.

Sort Characters By Frequency turns the counts themselves into the thing being sorted. H-Index is the same shape in academic clothing, counting how many papers have at least each citation count.

Maximum Gap is the hard one and introduces the next idea along. When the range is too big to count every value, group values into buckets and count those instead.

Common mistakes

Using it when the range is enormous. Counting across a range of two billion to sort ten items is far worse than just sorting them.

Forgetting negative values, which do not fit an array position without shifting everything first.

Losing the original order of equal items. Plain counting sort rebuilds from counts and throws that away. Keeping it needs the running total version, which places items from right to left.

Off-by-one mistakes in the running totals. Almost every bug here is that.