Counting Sort

Counting sort sorts by counting how many times each value appears. It does not compare values against each other.

It is useful when the values are integers from a limited range.

Core Idea

Instead of asking which of two values is smaller, counting sort builds a frequency table. The sorted output is then reconstructed from those counts.

If there are n values and the value range has size k, the time complexity is O(n + k).

Python Example

def counting_sort(values, max_value):
    counts = [0] * (max_value + 1)
 
    for value in values:
        counts[value] += 1
 
    result = []
    for value, count in enumerate(counts):
        result.extend([value] * count)
 
    return result

This version assumes all values are integers from 0 to max_value.

Common Confusions

Counting sort is not a general replacement for comparison sorting. If the value range is huge, the counts array may be too large.

The value range matters separately from the number of input items. A small n with a massive k can be a poor fit.

When To Use It

Use counting sort when values are discrete, the range is small enough, and counting frequencies is cheaper than comparing and rearranging values.