AI Hints
Home›DSA in Python Tutorial›Counting Sort and Practice
DSA in Python · Lesson 58 of 132

Counting Sort

Sorting without comparing.

⏱ 2 min read▶ Video at 1:07:43🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

Every sort so far compares items. Comparison sorts can never beat O of N log N. But if your values are small whole numbers, like exam marks from zero to a hundred, you can sort without comparing at all, by counting.

Counting Sort
From the video: Counting Sort
  • Comparison sorts: O(n log n) at best
  • Small whole numbers?
  • Sort by counting

Count, then rebuild

Make one counter for every possible value. Go through the data once, and add one to the counter for each value. Then walk through the counters in order, and write each value out as many times as it was counted. Run it.

counting_sort.pypython
def counting_sort(nums, max_value):
    counts = [0] * (max_value + 1)
    for n in nums:
        counts[n] += 1
    result = []
    for value, count in enumerate(counts):
        result.extend([value] * count)
    return result

print(counting_sort([4, 1, 3, 4, 0, 2, 1, 4], 4))
Output
[0, 1, 1, 2, 3, 4, 4, 4]

When counting sort wins

Counting sort is O of N plus K, where K is the range of values. For marks out of a hundred, or ages, that's effectively O of N, faster than any comparison sort. But if the values range up to a billion, you'd need a billion counters, so it's useless there.

keyvalue
TimeO(n + k)
kthe range of values
Great formarks, ages, small ranges
Bad forhuge ranges, decimals, text

Summary

Counting sort counts each value, and rebuilds the list, in O of N plus K. It only works for small ranges of whole numbers. Next, a practice problem where sorting is the key step.

Key takeaways
  • Count each value
  • Rebuild in order
  • O(n + k)
Next up: Practice: Merge Intervals — sort first, then sweep