AntInLoop

Counting Sort Algorithm

Counting Sort is a stable, non-comparison integer sorting algorithm that runs in linear O(n + k) time when input keys fall within a known, bounded integer range.

Difficulty: Easy · Interactive Visualizer · C++ / Python / Java / JS Code

Counting Sort Algorithm

Counting Sort is a non-comparison sorting algorithm that breaks the $\Omega(n \log n)$ comparison lower bound by avoiding element-to-element comparisons altogether. When keys are integers in a small known range $[0, K]$, it counts how many times each value appears, converts those counts into prefix sums (starting/ending positions), and places each element directly into its sorted slot.

At a Glance

| Property | Value |

| :--- | :--- |

| Best-Case Time | $O(n + K)$ |

| Average-Case Time | $O(n + K)$ |

| Worst-Case Time | $O(n + K)$ |

| Auxiliary Space | $O(n + K)$ |

| In-Place? | No |

| Stable? | Yes (when placing elements right-to-left) |

| Comparison-Based? | No |

| Best Used When | Integer (or small discrete) keys with $K = O(n)$, or as the stable pass inside Radix Sort |

---

How It Works

1. Allocate count[0..K] initialized to 0.

2. Frequency Pass: For each element x in A, increment count[x].

3. Prefix-Sum Pass: For i = 1..K, set count[i] += count[i - 1]. Now count[v] tells you the 1-based ending position of value v in the sorted output.

4. Stable Placement Pass (Right-to-Left): Walk i from n - 1 down to 0, place A[i] at output[count[A[i]] - 1], and decrement count[A[i]].

procedure countingSort(A, K):
    count = array of K + 1 zeros
    output = array of length(A)
    for x in A:
        count[x] += 1
    for i = 1 to K:
        count[i] += count[i - 1]
    for i = length(A) - 1 down to 0:
        output[count[A[i]] - 1] = A[i]
        count[A[i]] -= 1
    return output

Step-by-Step Trace

Sorting A = [4, 2, 2, 8, 3, 3, 1] with $K = 8$:

  • Frequencies (count[0..8]): [0, 1, 2, 2, 1, 0, 0, 0, 1]
  • Prefix sums: [0, 1, 3, 5, 6, 6, 6, 6, 7]
  • Value 1 ends at index 0 (count[1] - 1)
  • Value 2 ends at index 2, value 3 ends at index 4, etc.
  • Right-to-left placement:
  • 1 → output[0], 3 → output[4], 3 → output[3], 8 → output[6], 2 → output[2], 2 → output[1], 4 → output[5]
  • Result: [1, 2, 2, 3, 3, 4, 8]

---

Complexity & Key Insights

  • Why Right-to-Left Matters: Iterating A from n - 1 down to 0 places later occurrences of equal keys into the rightmost remaining slots for that key, guaranteeing stability. Stability is essential when Counting Sort is used as a subroutine in Radix Sort or when sorting key-value objects.
  • Handling Negative Numbers: Shift every value by offset = -minVal so the range becomes $[0, \text{maxVal} - \text{minVal}]$.
  • When NOT to use it: If $K \gg n$ (for example, sorting $1{,}000$ numbers in $[0, 10^9]$), the count array would require billions of entries—use Radix Sort or a comparison sort instead.

---

Practice Problems

Easy

1. Sort an Array of Non-Negative Integers

Given an array of non-negative integers in $[0, K]$, sort it stably in $O(n + K)$ time.

Approach: Frequency count → prefix sum → reverse placement pass. Time: $O(n + K)$. Space: $O(n + K)$.

<details>

<summary>Show C++ Solution</summary>

#include <iostream>
#include <vector>

void countingSort(std::vector<int>& arr, int K) {
    int n = static_cast<int>(arr.size());
    if (n <= 1) return;

    std::vector<int> count(K + 1, 0);
    std::vector<int> output(n);
    for (int x : arr) ++count[x];
    for (int i = 1; i <= K; ++i) count[i] += count[i - 1];
    for (int i = n - 1; i >= 0; --i) {
        output[--count[arr[i]]] = arr[i];
    }
    arr = std::move(output);
}

int main() {
    std::vector<int> arr = {4, 2, 2, 8, 3, 3, 1};
    countingSort(arr, 8);
    for (int x : arr) std::cout << x << " ";
    std::cout << "\n";
    return 0;
}

</details>

2. Sort a Lowercase String in $O(n)$

Given a string of lowercase English letters ('a'–'z'), return the sorted string in $O(n)$ time.

Approach: Since $K = 26$ is a constant, count occurrences of each character and rebuild the string directly. Time: $O(n)$. Space: $O(1)$ extra (excluding output).

<details>

<summary>Show C++ Solution</summary>

#include <array>
#include <iostream>
#include <string>

std::string countingSortString(const std::string& s) {
    std::array<int, 26> count{};
    for (char c : s) ++count[c - 'a'];

    std::string out;
    out.reserve(s.size());
    for (int i = 0; i < 26; ++i) {
        out.append(count[i], static_cast<char>('a' + i));
    }
    return out;
}

int main() {
    std::cout << countingSortString("dbcaab") << "\n";
    return 0;
}

</details>

---

Intermediate

3. Sort Signed Integers (Including Negatives)

Sort an array containing negative, zero, and positive integers with a bounded span maxVal - minVal.

Approach: Find minVal and maxVal using std::minmax_element, shift all keys by -minVal, and run Counting Sort on [0, maxVal - minVal]. Time: $O(n + (\text{maxVal} - \text{minVal}))$. Space: $O(n + (\text{maxVal} - \text{minVal}))$.

<details>

<summary>Show C++ Solution</summary>

#include <algorithm>
#include <iostream>
#include <vector>

void countingSortSigned(std::vector<int>& arr) {
    if (arr.size() <= 1) return;
    auto [minIt, maxIt] = std::minmax_element(arr.begin(), arr.end());
    int minVal = *minIt;
    int range = *maxIt - minVal + 1;

    std::vector<int> count(range, 0);
    std::vector<int> output(arr.size());
    for (int x : arr) ++count[x - minVal];
    for (int i = 1; i < range; ++i) count[i] += count[i - 1];
    for (int i = static_cast<int>(arr.size()) - 1; i >= 0; --i) {
        output[--count[arr[i] - minVal]] = arr[i];
    }
    arr = std::move(output);
}

int main() {
    std::vector<int> arr = {-5, -10, 0, -3, 8, 5, -1, 10};
    countingSortSigned(arr);
    for (int x : arr) std::cout << x << " ";
    std::cout << "\n";
    return 0;
}

</details>

4. Counting Sort as the Stable Digit Pass in LSD Radix Sort

Sort non-negative integers by repeatedly applying Counting Sort on each decimal digit from least significant to most significant.

Approach: Each digit is in $[0, 9]$, so Counting Sort runs in $O(n + 10) = O(n)$ per digit. Stability preserves the ordering of less-significant digits. Time: $O(d \cdot n)$ where $d$ is the number of digits.

<details>

<summary>Show C++ Solution</summary>

#include <algorithm>
#include <array>
#include <iostream>
#include <vector>

void countingSortByDigit(std::vector<int>& arr, long long exp) {
    int n = static_cast<int>(arr.size());
    std::array<int, 10> count{};
    std::vector<int> output(n);

    for (int x : arr) ++count[(x / exp) % 10];
    for (int i = 1; i < 10; ++i) count[i] += count[i - 1];
    for (int i = n - 1; i >= 0; --i) {
        int digit = static_cast<int>((arr[i] / exp) % 10);
        output[--count[digit]] = arr[i];
    }
    arr = std::move(output);
}

void radixSort(std::vector<int>& arr) {
    if (arr.size() <= 1) return;
    int maxVal = *std::max_element(arr.begin(), arr.end());
    for (long long exp = 1; maxVal / exp > 0; exp *= 10) {
        countingSortByDigit(arr, exp);
    }
}

int main() {
    std::vector<int> arr = {170, 45, 75, 90, 802, 24, 2, 66};
    radixSort(arr);
    for (int x : arr) std::cout << x << " ";
    std::cout << "\n";
    return 0;
}

</details>

---

Hard

5. Top $k$ Frequent Elements in $O(n)$ (Frequency Counting / Bucket Trick)

Given an array of $n$ integers, return the $k$ most frequent elements in $O(n)$ time (faster than $O(n \log k)$ heap-based approaches).

Approach: Because every element's frequency is at most $n$, the frequency values themselves lie in $[1, n]$. Group distinct numbers into byFreq[f] buckets indexed by frequency f, then scan f from n down to 1 and collect the first k elements. Time: $O(n)$. Space: $O(n)$.

<details>

<summary>Show C++ Solution</summary>

#include <iostream>
#include <unordered_map>
#include <vector>

std::vector<int> topKFrequent(const std::vector<int>& nums, int k) {
    std::unordered_map<int, int> freq;
    for (int x : nums) ++freq[x];

    int n = static_cast<int>(nums.size());
    std::vector<std::vector<int>> byFreq(n + 1);
    for (const auto& [val, count] : freq) {
        byFreq[count].push_back(val);
    }

    std::vector<int> res;
    res.reserve(k);
    for (int f = n; f >= 1 && static_cast<int>(res.size()) < k; --f) {
        for (int val : byFreq[f]) {
            res.push_back(val);
            if (static_cast<int>(res.size()) == k) break;
        }
    }
    return res;
}

int main() {
    std::vector<int> nums = {1, 1, 1, 2, 2, 3};
    for (int x : topKFrequent(nums, 2)) std::cout << x << " ";
    std::cout << "\n";
    return 0;
}

</details>

---

Related Algorithms

  • Radix Sort — extends Counting Sort to large integer ranges by sorting one digit at a time.
  • Bucket Sort — generalizes counting into value-range buckets for floating-point and continuous distributions.
  • Merge Sort — stable $O(n \log n)$ alternative when the key range $K$ is huge or keys are not integers.