Counting Sort Algorithm: Non-Comparison Sort, O(n+k), Stable, and Integer Sorting (2026)
Counting Sort is a non-comparison-based sorting algorithm that sorts integers by counting the occurrences of each unique element. It uses this count information to place elements directly into their correct positions in the output array. Unlike comparison sorts (Bubble, Merge, Quick), Counting Sort can achieve linear time complexity under certain conditions.
This tutorial covers the algorithm steps, time and space complexity (O(n+k)), the stable sorting property, and the constraints that make Counting Sort applicable only for integer data with a limited range. Code examples in C++, Java, and Python are provided.
Algorithm Steps and Complexity
Counting Sort works in three phases. First, find the range (max - min) of the input array and create a count array of that size, initialized to zero. Second, count the frequency of each element by iterating through the input and incrementing count[arr[i] - min]. Third, transform the count array into a prefix sum array, then iterate the input in reverse order, placing each element in its correct position in the output array using the prefix sum to determine the index. This reverse pass ensures stability.
Time complexity is O(n + k) where n is the number of elements and k is the range of input values. Space complexity is O(n + k) for the count and output arrays. Counting Sort is stable, meaning equal elements retain their original relative order.
// C++
void countingSort(int arr[], int n) {
int maxVal = *max_element(arr, arr+n);
int minVal = *min_element(arr, arr+n);
int range = maxVal - minVal + 1;
vector count(range, 0), output(n);
for(int i=0; i=0; i--) {
output[count[arr[i]-minVal]-1] = arr[i];
count[arr[i]-minVal]--;
}
for(int i=0; i=0; i--) {
output[count[arr[i]-min]-1] = arr[i];
count[arr[i]-min]--;
}
System.arraycopy(output, 0, arr, 0, arr.length);
}
// Python
def counting_sort(arr):
if not arr: return arr
mn, mx = min(arr), max(arr)
rng = mx - mn + 1
cnt = [0] * rng
for x in arr: cnt[x-mn] += 1
for i in range(1, rng): cnt[i] += cnt[i-1]
out = [0] * len(arr)
for x in reversed(arr):
out[cnt[x-mn]-1] = x
cnt[x-mn] -= 1
return out When to Use Counting Sort
Counting Sort is ideal when the range of input values (k) is not significantly larger than the number of elements (n). For example, sorting a million numbers between 0 and 1000 is O(n + k) ≈ O(1,001,000), which is much faster than O(n log n) ≈ O(20,000,000). However, if k is large (e.g., sorting numbers from 0 to 10^9), Counting Sort becomes impractical due to memory requirements.
Counting Sort only works for integer (or discretely mappable) data. It is a key component of Radix Sort, which sorts by individual digits to handle arbitrary integer ranges efficiently. Counting Sort is also used in data compression (Burrows-Wheeler transform) and in situations where the input domain is known and bounded.
// C++ — counting sort works best with small range
// Input: [4, 2, 2, 8, 3, 3, 1]
// Range: 1-8 (k=8), n=7 -> O(15)
// Java — used in Radix Sort
void radixSort(int[] arr) {
int max = Arrays.stream(arr).max().getAsInt();
for(int exp=1; max/exp>0; exp*=10)
countingSortByDigit(arr, exp);
}
// Python — counting sort on small integer range
arr = [random.randint(0, 100) for _ in range(1000)]
arr = counting_sort(arr) # fast because k=100 is smallFrequently Asked Questions
What is the time complexity of Counting Sort?
O(n + k) where n is the number of elements and k is the range of input values. When k = O(n), Counting Sort runs in linear time.
What is the limitation of Counting Sort?
It only works for integer data (or data that can be mapped to integers) and becomes inefficient when the range k is very large relative to n, both in time and memory.
Originally published on Ayodhyyya. Last updated June 1, 2026.