ArraysLesson 9Free preview

DSA Counting Sort

This lesson is part of DSA · All levels

Summary

Counting sort sort by calculating the occurrence of each value using a special array, then rearranging based on the accumulation of the count. It does not compare elements with each other, so it can reach O(n + k) with k as a value range. The basic requirement is that the range of values should not be too large for the amount of data.

Key points

Non-comparison algorithm based on frequency of occurrence of values
Complexity O(n + k) with k maximum range
Requires a range-sized array of counts
It's not efficient when the range of values is too wide compared to the number of elements.

Full lesson

Code examples and quizzes

Full lessons, code examples, and quizzes are available to subscribers. 5 questions.