Counting Sort: Basic Concept
What You'll Learn
You'll discover how counting sort achieves linear-time sorting by counting how many times each integer appears, rather than comparing values.
Why Comparison-Based Sorting Has a Limit
You've seen that comparison-based algorithms like Quicksort, Mergesort, and Heapsort all have a best-case time complexity of O(n log n). This is actually a mathematical lower bound—you cannot do better using comparisons alone. But what if we break free from comparisons entirely?
The Counting Sort Approach
Counting sort works on integers within a known range by using a fundamentally different strategy:
- Count occurrences: Create a count array where each index represents a possible value, and store how many times that value appears in the input
- Use counts to place elements: Convert those counts into positions, then place each element directly into its final sorted position
An Analogy
Imagine sorting exam scores (0–100). Instead of comparing scores pairwise, you could:
- Set up 101 boxes labeled 0 through 100
- Walk through the scores once, dropping each into its matching box
- Read the boxes in order: 0, 1, 2, ... 100
No comparisons needed! You've sorted in O(n + k) time, where n is the number of elements and k is the range of values.
When It Works
Counting sort is ideal when:
- You're sorting integers (or can map items to integers)
- The range of values (k) is not much larger than the number of elements (n)
- You need linear time and stability matters
Key Takeaway: Counting sort breaks the O(n log n) barrier by counting occurrences instead of comparing, achieving O(n + k) time when sorting integers in a limited range.