Counting Sort Implementation

Problem Statement

Sort an array of integers in a small known range using counting sort: count how many times each value appears, then emit the values in order.

Example

Input:  [4, 2, 2, 8, 3, 3, 1]
Counts: 1->1, 2->2, 3->2, 4->1, 8->1
Output: [1, 2, 2, 3, 3, 4, 8]

Approach

Counting sort is a non-comparison sort. Find the value range, tally counts in a frequency array indexed by value, then overwrite the input in ascending order. It is linear when the range k is comparable to n, and becomes stable when implemented with cumulative counts placing elements from right to left.

Complexity

• Time: O(n + k), where k is the value range
• Space: O(k)

Solution Code

Python

def counting_sort(arr):
    if not arr:
        return arr
    lo, hi = min(arr), max(arr)
    count = [0] * (hi - lo + 1)
    for x in arr:
        count[x - lo] += 1
    idx = 0
    for value, c in enumerate(count):
        for _ in range(c):
            arr[idx] = value + lo
            idx += 1
    return arr

Java

void countingSort(int[] arr) {
    if (arr.length == 0) return;
    int lo = arr[0], hi = arr[0];
    for (int x : arr) { lo = Math.min(lo, x); hi = Math.max(hi, x); }
    int[] count = new int[hi - lo + 1];
    for (int x : arr) count[x - lo]++;
    int idx = 0;
    for (int v = 0; v < count.length; v++)
        while (count[v]-- > 0) arr[idx++] = v + lo;
}

C++

void countingSort(vector<int>& arr) {
    if (arr.empty()) return;
    int lo = *min_element(arr.begin(), arr.end());
    int hi = *max_element(arr.begin(), arr.end());
    vector<int> count(hi - lo + 1, 0);
    for (int x : arr) count[x - lo]++;
    int idx = 0;
    for (int v = 0; v < (int)count.size(); v++)
        while (count[v]-- > 0) arr[idx++] = v + lo;
}

Key Takeaways

• Counting sort beats O(n log n) when the value range k is small.
• It is only practical for integers (or keys mappable to a small range).
• Reference: CLRS, Ch. 8; Wikipedia, "Counting sort".