Time Complexity
Best: O(n + k)
Avg: O(n + k)
Worst: O(n + k)
Counting Sort is a non-comparison-based sorting algorithm. It counts the occurrences of each value and uses arithmetic to determine positions.
How it works:
1. Find the range of input values (min to max)
2. Create a count array to store frequency of each value
3. Modify count array to store cumulative counts
4. Build the output array by placing elements at their correct positions
Time Complexity:
Best: O(n + k)
Average: O(n + k)
Worst: O(n + k)
where k is the range of input values
Space Complexity: O(n + k)
Properties:
- Stable sort
- Not in-place
- Not comparison-based
- Very efficient when k is small relative to n
Counting Sort is ideal for sorting integers within a known, small range. It's used as a subroutine in Radix Sort.
Related algorithms
Frequently asked questions
- What is Counting Sort?
- Counting Sort is a non-comparison-based sorting algorithm. It counts the occurrences of each value and uses arithmetic to determine positions.
- What is the complexity of Counting Sort?
- Time (average): O(n + k) · Space: O(n + k)
- Who is this Counting Sort visualizer for?
- The Counting Sort visualization targets intermediate-level learners in the Sorting category. Useful for students, interview prep, and hands-on review.
- What algorithms are related to Counting Sort?
- In the same category (Sorting) you can explore: Bubble Sort, Selection Sort, Insertion Sort. Each has an interactive visualization.