Counting Sort Algorithm

Counting Sort is a non-comparison sorting algorithm that sorts integers by counting how many times each value appears.

What is Counting Sort?

Counting Sort is a non-comparison sorting algorithm used for sorting integers when the range of possible values is not too large. Instead of comparing elements with each other, it counts how many times each value appears.

After building the frequency count, the algorithm reconstructs the sorted array by placing each value according to its count. A stable version uses prefix sums to determine the final position of each element.

Core Intuition

If the input contains only a small range of integer values, we do not need to compare every pair of elements. We can simply count how many times each number occurs.

For example, if the array contains three 2s, one 3, and two 5s, the sorted order must place all 2s first, then 3, then all 5s. Counting Sort uses this idea directly.

Counting Sort Algorithm Steps

1. Find the range.
   Identify the minimum and maximum values, or assume a known range.
2. Create a count array.
   Each index represents a value from the input range.
3. Count frequencies.
   For every number, increment its corresponding count.
4. Build prefix counts for stable sorting.
   Prefix counts tell where each value should end in the output array.
5. Place elements in output.
   Traverse the input from right to left to preserve stability.
6. Copy back if needed.
   The output array contains the sorted result.

Interactive Counting Sort Visualization

Use the visualization below to see how Counting Sort builds a frequency array, converts it into prefix counts, and places elements into their final sorted positions.

Dry Run Example

Suppose we want to sort:

[4, 2, 2, 8, 3, 3, 1]

Step 1: Find the range

• Minimum value = 1
• Maximum value = 8
• We need counts for values from 1 to 8.

Step 2: Count frequencies

• The frequency of each value is:
  
Value: 1 2 3 4 5 6 7 8
Count: 1 2 2 1 0 0 0 1

Step 3: Build the sorted output

• One copy of 1 → [1]
• Two copies of 2 → [1, 2, 2]
• Two copies of 3 → [1, 2, 2, 3, 3]
• One copy of 4 → [1, 2, 2, 3, 3, 4]
• One copy of 8 → [1, 2, 2, 3, 3, 4, 8]

The array is now sorted.

Counting Sort Code in Python

This implementation handles non-negative and negative integers by offsetting values using the minimum element. It uses prefix counts to keep the sort stable.

def counting_sort(arr):
    if not arr:
        return arr

    min_val = min(arr)
    max_val = max(arr)
    range_size = max_val - min_val + 1

    count = [0] * range_size
    output = [0] * len(arr)

    # Count frequency of each value.
    for num in arr:
        count[num - min_val] += 1

    # Convert counts into prefix counts.
    for i in range(1, range_size):
        count[i] += count[i - 1]

    # Place elements into output from right to left for stability.
    for i in range(len(arr) - 1, -1, -1):
        num = arr[i]
        count[num - min_val] -= 1
        output[count[num - min_val]] = num

    return output


print(counting_sort([4, 2, 2, 8, 3, 3, 1]))

Time and Space Complexity

When Should You Use Count Sort?

Interview Notes and Common Pitfalls

This section highlights the key ideas interviewers expect you to understand, especially when Counting Sort is useful and when it becomes inefficient.

What interviewers may expect you to know

• Counting Sort is not comparison-based.
• It can run in O(n + k), where k is the value range.
• It works best when k is not much larger than n.
• A basic counting version reconstructs values directly from frequencies.
• A stable version uses prefix sums and places elements from right to left.
• Counting Sort is commonly used inside Radix Sort.sed on divide and conquer.

Common mistakes

• Forgetting that Counting Sort requires integer-like keys.
• Ignoring negative numbers and indexing the count array incorrectly.
• Using Counting Sort when the value range is extremely large.
• Forgetting to convert counts into prefix counts for the stable version.
• Traversing left to right during output placement and accidentally breaking stability.
• Claiming the algorithm is always better than O(n log n) without considering k.

Related coding interview problems

• Sort Colors
• Top K Frequent Elements
• Frequency Sort
• Relative Sort Array
• Maximum Gap

Quick Quiz

Key Takeaways

• Counting Sort sorts by counting how many times each value appears.
• It is a non-comparison sorting algorithm.
• Its time complexity is O(n + k), where k is the value range.
• It is useful when values are integers and the range is small.
• A stable version uses prefix sums and right-to-left placement.
• It is often used as a building block for Radix Sort.