Counting sort for integer sorting in linear time

Sorting is one of those jobs that looks trivial until the dataset arrives. A list of twelve delivery priorities is no trouble; a million order records with the same handful of priority codes is a different engineering problem. Counting sort solves the second kind of problem by counting occurrences instead of repeatedly comparing values.

For integer keys drawn from a known, bounded range, the technique can run in O(n + k) time, where n is the number of values and k is the size of the value range. It does not violate the comparison-sorting lower bound: it relies on a different assumption, namely that values can be used directly as positions in a frequency table.

That assumption fits plenty of ordinary work in Australia. An online retailer might sort integer dispatch slots for customer collection around Sydney or Melbourne while couriers take parcels to regional centres. The informal description is simply chucking the numbers into order, but choosing the right algorithm still matters when the manifest contains thousands of orders.

Why integer keys change the cost model

A conventional comparison sort, such as merge sort or heap sort, generally requires O(n log n) comparisons. Counting sort spends additional memory to reduce the running time: it creates k counters, scans the input and emits each integer according to its count. Every value participates in a bounded amount of work rather than travelling through a comparison tree.

The technique is not appropriate for every dataset. For continuous measurements with a roughly even distribution, bucket sort is usually a better fit. Bucket sort distributes values among intervals before sorting each smaller group, whereas counting sort expects discrete integer keys and a manageable interval between the smallest and largest values.

Think of a transport analyst in Sydney who has aggregated Opal taps into hourly passenger totals. Counts might run from zero to several hundred, making them ideal integer keys. If one corrupted record contains a value such as 900,000, however, the frequency table must stretch from the minimum to that outlier. The memory-saving advantage can disappear in an instant.

Constructing the frequency table

The first design choice is how to represent the value range. If the minimum is low and the maximum is high, allocate high − low + 1 counters. Store the counter for a value x at index x − low. That offset makes negative integers work without separate branches: for [-2, 0, 3], the minimum is -2 and the corresponding counter indexes are 0, 2 and 5.

The second choice is whether to keep raw frequencies or cumulative totals. Raw frequencies reveal the distribution directly. Cumulative totals also identify each key’s final position in the output.

Consider Australian postcodes as a warning about representation. Darwin’s 0800 and Sydney’s 2000 are four-character codes, not merely the integers 800 and 2000. Integer sorting puts 800 first, whereas fixed-width code sorting preserves 0800 before 2000. If an application must retain leading zeros, sort the strings or retain the original codes separately while using a numeric key for ordering.

The version below uses cumulative totals and scans the input from right to left. This preserves the relative order of equal keys, a property called stability. With integer-only values that property is visually unremarkable, but it becomes important when the technique is adapted to sort records carrying extra fields, such as a delivery timestamp.

COUNTING-SORT(values)
    if values is empty:
        return empty list

    low ← minimum(values)
    high ← maximum(values)
    counts ← array of (high − low + 1) zeros

    for value in values:
        counts[value − low] ← counts[value − low] + 1

    for i from 1 to length(counts) − 1:
        counts[i] ← counts[i] + counts[i − 1]

    output ← array of length(values)

    for value in values from last to first:
        counts[value − low] ← counts[value − low] − 1
        output[counts[value − low]] ← value

    return output

Implementing the algorithm in Python

Here is a complete Python function for integer keys. It handles an empty list, supports negative values and leaves the original list unchanged.

def counting_sort(values):
    if not values:
        return []

    low = min(values)
    high = max(values)
    counts = [0] * (high - low + 1)

    for value in values:
        counts[value - low] += 1

    for index in range(1, len(counts)):
        counts[index] += counts[index - 1]

    output = [0] * len(values)

    for value in reversed(values):
        shifted = value - low
        counts[shifted] -= 1
        output[counts[shifted]] = value

    return output

For example, counting_sort([3, -2, 3, 1, -2]) returns [-2, -2, 1, 3, 3]. The output array is filled from the end using cumulative totals, so earlier copies of an equal key remain earlier in the result. The implementation uses reversed(values) to traverse the input without creating another list.

The time cost is O(n + k), where k is high − low + 1. Finding the bounds takes O(n), counting takes O(n), building cumulative totals takes O(k), and reconstruction takes O(n). The counters require O(k) extra space, while the returned list requires O(n). A narrow range uses little auxiliary memory; a huge range allocates a counter for every missing integer.

A linear asymptotic bound does not automatically make this Python implementation faster than the built-in sorted. Python executes that function in optimised native code and can exploit existing order. Benchmarking with representative values is sensible, particularly when the input is small or already nearly sorted.

Where counting sort fits in practice

Counting sort is most convincing when the key domain is dense relative to the number of records. Suppose n is one million and k is one thousand: counters for a thousand possible values are cheaper than a large comparison tree. If k becomes ten million because of two distant outliers, that same allocation becomes wasteful.

Good candidates

• Large batches of integers with a small, predictable span
• Duplicate-heavy data that a frequency table can compress effectively
• Integer-coded scores, ages or deliberately discretised measurements
• Stable sorting where equal keys must retain their input order

Cases to avoid

• Sparse values spread across an enormous numerical range
• Floating-point data unless it has been converted into meaningful bins
• Codes whose numeric and textual orders differ, including leading-zero identifiers
• Small collections where the built-in sorted function is simpler and fast enough

No rule applies in isolation. A small batch may favour the convenience of sorted, while a large, sparse range may call for radix sorting on fixed-width positive integers. If the task only requires grouping equal values, a dictionary can avoid the dense counter allocation altogether.

For another hands-on exercise with structured Python records, the guide to building a blockchain in Python offers a useful companion setting. It also reinforces a practical principle: consistent ordering begins with consistent data representation, whether the records describe blocks, orders or measurements.

Using integer order in data pipelines

Machine-learning pipelines often encode class labels, ordinal categories or binned measurements as integers. The site’s machine learning fundamentals provide useful background for understanding why those representations affect models and evaluation. Once a feature has been deliberately discretised into a small set of bins, its bin indices can be sorted with counting sort, provided the numerical order of the bins reflects the feature’s meaning. Arbitrary label encodings should not be treated as ordinal data.

An arvo collection schedule provides a more familiar example. In Melbourne, a small seller might sort integer pickup windows for an arvo collection and use the result to prepare courier labels. The same retailer may use different dispatch rules for metropolitan orders and regional deliveries, so sorting the correct integer field matters more than sorting an entire record. Repeated pickup windows compress neatly into a frequency table, while unusual surcharge values may be better handled separately.

In a streaming setting, the input may not fit comfortably in memory. Maintain counters as records arrive, update only the affected count and periodically reconstruct a sorted snapshot. This turns the static algorithm into incremental counting, though choosing a stable key and a sensible range remains essential. For very large ranges, radix sorting on fixed-width integers or a dictionary-based frequency map can avoid allocating one slot per possible value.