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
1ends at index0(count[1] - 1) - Value
2ends at index2, value3ends at index4, 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
Afromn - 1down to0places 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 = -minValso 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
countarray 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.