Definition

Counting sort is a non-comparison algorithm that sorts by counting occurrences. Since it uses counting instead of comparisons, it can sort in O(n+k) time when value range (k) is small.

Key Characteristics

• ✓No comparisons - Sorts by counting, not comparing elements
• ✓O(n+k) time - n is element count, k is value range
• ✓Stable sort - Relative order of equal values preserved (with reverse placement)
• ✓Constraints - Only non-negative integers, inefficient if k is large

Time Complexity