Overview
Counting Sort builds a count table for a limited value range and uses those counts to place values in order.
CoreSource checked
Counting Sort
Sorts integer values by counting how many times each value appears.
Quick Facts
Compact metadata for implementation and discovery.
- Category
- Sorting
- Difficulty
- Beginner
- Family
- Distribution Sort
- Tier
- Core
- Status
- Verified
- Review
- Source Checked
- Sources
- 1
- Formulas
- 0
- Relationships
- 3
- Code example
- Ready
- Visualization
- Ready
Core Concepts
integer key rangestable orderingdistribution sortordering invariantcomparison or key rulearray rearrangement
Quick facts
Complexity
Runtime and memory behavior at a glance.
Best
O(n + k)
Average
O(n + k)
Worst
O(n + k)
Space
O(k)
When to Use
- Use Counting Sort when you need to count occurrences of each value.
- Use it for sorting small integer ranges with inputs like integer array.
- Use it when ordered output makes later searching, ranking, or presentation easier.
- Use it when the Distribution Sort tradeoff is acceptable for the problem size.
When Not to Use
- Avoid it when values are not bounded integers or cannot be mapped cleanly to integer keys.
- Avoid it when a partial order, top-k result, or streaming approach would answer the question with less work.
- Avoid it when the required output is not sorted array.
What It Does
- Counts occurrences of each value
- Reconstructs the list from the counts
Use Cases
- Sorting small integer ranges
- Sorting grades or buckets
- Supporting radix sort
Inputs
- Integer array
- Known value range
Outputs
- Sorted array
Pseudocode
- 1.Create a count array for the value range
- 2.Count each input value
- 3.Convert counts into positions if stable output is needed
- 4.Place each value into its sorted position
- 5.Return the output array
Canonical Example
- Input
- values = [5, 1, 4, 2]
- Output
- values = [1, 2, 4, 5]
- Explanation
- Counting Sort: The algorithm reorders the values so later operations can read them in ascending order.
Implementation Notes
- Keep the input contract explicit: Integer array; Known value range.
- Use this step as the implementation spine: Create a count array for the value range.
- Then preserve the next state change: Count each input value.
- Test with empty input, one item, duplicates, and already sorted values.
Common Pitfalls
- Counting Sort is efficient only when the value range is not much larger than the input.
- Assuming stability without checking the implementation can reorder equal keys.
- Forgetting to define how equal values and custom comparison rules should behave.
- Returning sorted array without handling empty, invalid, or boundary inputs.
Interactive Mechanism Walkthrough
Array Partition & Ordering TraceShow input values filling count buckets and then rebuilding the sorted list.
38[0]
14[1]
52[2]
23[3]
61[4]
19[5]
44[6]
29[7]
Step 1 of 5: Create a count array for the value range
counting-bucketsNotes
Counting Sort operates in O(n + k) time and O(k) space within the Distribution Sort family. Often compared with Radix Sort and Merge Sort.
Sources (1)
What each reference supports for this entry.
Introduction to Algorithms (CLRS)
BookTextbook support for Counting Sort invariants, recurrences, relaxation rules, or asymptotic analysis.
Open sourceExplore Next
Good next jumps from the relationship graph, ranked for useful discovery.
Relationships
View full relationship pageUsed byRadix Sort
Radix sort commonly uses counting sort as the stable pass over each digit or key fragment.
Related Algorithms
Tags
Integer DataStable SortClassic