Course contentsShow
← Computer Science
Lesson 788 of 2,87218. Sorting AlgorithmsFree lesson

Counting Sort: Basic Concept

Understanding counting sort's approach of tallying occurrences to sort integers in linear time.

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:

  1. Count occurrences: Create a count array where each index represents a possible value, and store how many times that value appears in the input
  2. 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.