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).

Counting sort changes the model of sorting. Comparison sorts learn order by comparing elements. Counting sort uses the fact that possible values are known and countable.

Function Contract

counting_sort(values, max_value) expects every value to be an integer between 0 and max_value, inclusive.

It returns a new sorted list. The function is not valid for negative numbers or values greater than max_value unless the indexing scheme is changed.

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.

Step-by-Step Example

For:

values = [3, 1, 2, 1, 3]

the counts array becomes:

value: 0 1 2 3
count: 0 2 1 2

The output is reconstructed by writing 1 twice, 2 once, and 3 twice:

[1, 1, 2, 3, 3]

Why It Works

If the count for value x is correct, then the sorted result must contain exactly that many copies of x. Reconstructing values in increasing order produces a sorted list because all smaller values are emitted before all larger values.

Complexity and Range

The algorithm scans n input values and then scans k possible values. That gives O(n + k) time and O(k) extra space.

This is efficient only when k is reasonably small compared with the input and memory limits.

Failure Example

If values = [1, 1000000], the input has only two items but the count array needs one million and one slots. Counting sort is a poor fit because the value range is huge compared with the input size.

If values contains -1, the simple indexing version is invalid because counts[-1] does not mean the count for value -1 in the intended table.

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.

The simple version above does not handle negative numbers directly. A shifted index can handle them, but the range size still matters.

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.

Do not use counting sort when values are arbitrary objects, strings with no bounded ranking, or integers spread across a huge range.

The Main Point

Counting sort is fast only because the possible values are limited and countable. Its cost depends on both the number of items and the value range.