Abstract flowing gradient in deep indigo and blue tones, smooth and luminous, evoking a modern digital learning atmosphere

Computer Science and programming articles. We do not sell courses.

Counting Sort Explained: Linear Time Sorting Without Comparisons

When sorting integers, computer scientists usually reach for comparison-based algorithms like merge sort or quicksort. These methods rely on comparing pairs of elements, which imposes a mathematical floor of O(n log n) on their running time. Counting sort breaks that ceiling by skipping comparisons entirely, using the actual values of the elements as indices into an auxiliary array. The result is a sorting routine that runs in O(n + k) time, where n is the number of items and k is the range of possible values.

For learners working through algorithm courses at universities in Melbourne, Sydney, or Brisbane, counting sort is often the first non-comparison sort they encounter. It demonstrates a crucial principle in algorithm design: when you can exploit extra structure in your data, you can outperform general-purpose methods. The technique also appears as a building block for radix sort and bucket sort, making it a foundational topic for anyone serious about linear time sorting.

The core idea behind counting sort

At its heart, counting sort assumes that the input consists of integers drawn from a known, bounded range. If you are sorting the ages of people in a room, you know the values lie between 0 and 120. If you are sorting student marks for a subject at the University of Sydney, the marks fit within 0 to 100. This bounded range is what allows the algorithm to operate in linear time.

The algorithm works by counting how many times each value appears in the input. Those counts are then used to place each element directly into its correct position in a sorted output array. Because every element is written exactly once and every possible value is scanned once, the total work grows linearly with the input size plus the range of values.

This approach trades space for time. The auxiliary count array has a length equal to the range k, and the output array holds n elements. When k is not much larger than n, the extra memory is a small price to pay for escaping the comparison barrier. Understanding this trade-off is essential for any programmer considering counting sort for production code, and it parallels trade-offs you see elsewhere in machine learning, such as when computing the Shapley value for feature importance.

How the algorithm works step by step

A run of counting sort proceeds in three clear phases. First, the algorithm scans the input array and increments a counter for each value it encounters. After this pass, counter[i] holds the number of times the value i appears in the input.

The second phase transforms the count array into a prefix sum array. Each entry counter[i] is replaced by the sum of all previous counts, which gives the position in the output array where the value i should end. This step ensures that elements are placed stably, meaning equal values retain their original relative order.

The third phase walks through the input array in reverse, placing each element at the position indicated by the prefix sum array, then decrementing that position. The reverse walk is what preserves stability. After the final pass, the output array holds the elements in sorted order, and the original input remains untouched.

Pseudocode and complexity analysis

Here is a clean pseudocode version that mirrors the three phases described above:

function countingSort(A, k):
    C = array of zeros with length k + 1
    B = output array of length len(A)

    for i in 0 .. len(A) - 1:
        C[A[i]] = C[A[i]] + 1

    for i in 1 .. k:
        C[i] = C[i] + C[i - 1]

    for i in len(A) - 1 down to 0:
        B[C[A[i]] - 1] = A[i]
        C[A[i]] = C[A[i]] - 1

    return B

The time complexity is O(n + k): the first loop runs n times, the second runs k times, and the third runs n times. The space complexity is O(n + k), accounting for both the count array and the output array. When k equals O(n), the algorithm runs in true linear time, which is faster than any comparison-based sort.

Stability is one of counting sort's most valuable properties. Many sorting applications, such as ordering student records by one field then another, require a stable sort. Counting sort delivers this without extra effort, unlike quicksort, which needs careful partitioning to remain stable. For a deeper look at the mathematics that underpin another stable and elegant algorithm, the article on the mathematics behind support vector machines offers a useful parallel.

Comparing counting sort with other sorting algorithms

Algorithm Best time Average time Worst time Space Stable Comparison-based
Counting sort O(n + k) O(n + k) O(n + k) O(n + k) Yes No
Merge sort O(n log n) O(n log n) O(n log n) O(n) Yes Yes
Quick sort O(n log n) O(n log n) O(n²) O(log n) No Yes
Heap sort O(n log n) O(n log n) O(n log n) O(1) No Yes
Radix sort O(nk) O(nk) O(nk) O(n + k) Yes No
Bubble sort O(n) O(n²) O(n²) O(1) Yes Yes

The table highlights why counting sort is a specialised tool rather than a general replacement for comparison sorts. Its linear time only applies when k is small, and its space cost grows with k. For most general-purpose sorting tasks in production systems, merge sort or a well-implemented quicksort remains the safer default.

Implementation in Python

Python's standard library makes counting sort easy to write and even easier to read. The following implementation works on any list of non-negative integers within a known range.

def counting_sort(arr, k):
    count = [0] * (k + 1)
    output = [0] * len(arr)

    for value in arr:
        count[value] += 1

    for i in range(1, k + 1):
        count[i] += count[i - 1]

    for i in range(len(arr) - 1, -1, -1):
        output[count[arr[i]] - 1] = arr[i]
        count[arr[i]] -= 1

    return output

To handle negative integers, you can shift the values by subtracting the minimum element before sorting, then shifting back after sorting. For floating-point numbers, you would need to discretise the values first, which often negates the linear time advantage unless the precision is small.

If you are preparing for technical interviews at firms like Canva or Atlassian, both headquartered in Sydney, practising counting sort implementations is worthwhile. Interviewers often ask candidates to modify the algorithm, such as making it work in place or extending it to handle strings of equal length.

Limitations and practical applications

Counting sort shines when the range of values is small relative to the number of elements. Sorting a million exam scores between 0 and 100 is a perfect fit. Sorting a million values drawn from a range of 0 to one million is borderline, because the count array becomes large. Sorting a million 64-bit integers is impractical, since k would be roughly 18 quintillion.

The algorithm also requires direct access to the values as indices. This rules out general objects unless you can map them to integer keys. Strings can be sorted character by character using a variant of counting sort, but the technique is most natural for numeric data.

Memory pressure is another concern. For very large datasets, such as the kind processed by the Australian Bureau of Statistics when publishing census results, an auxiliary array of size k may not fit in cache or even in RAM. In such settings, external sorting algorithms that use disk-backed merge steps are usually preferred over counting sort.

Counting sort still appears in a surprising number of real-world systems. Database engines use it when sorting small integer keys during query execution. Graphics applications use it for histogram equalisation, which redistributes pixel intensities across an image. In Australia, electoral counts benefit from counting sort logic, since the Australian Electoral Commission tallies first-preference votes by candidate, a counting operation followed by ordering.

Recommendations for using counting sort effectively