Counting Sort
Last updated
Counting sort is a non-comparison sort for integers in a known, limited range. It counts how many times each value appears, then uses those counts to write every value directly into its sorted position - no comparisons needed. Press play above to watch the values get tallied and then placed back in order.
Counting sort runs in O(n + k) time, where k is the range of the input values. When k is not much larger than n it is extremely fast and can beat O(n log n) comparison sorts, but if the value range is huge the O(k) count array makes it impractical.
Time & space complexity
| Case | Complexity | Notes |
|---|---|---|
| Time | O(n + k) | n elements, k = value range |
| Space | O(n + k) | Count array + output array |
| Stable | Yes | When placed right-to-left using prefix sums |
| Comparison? | No | Sorts by counting, not comparing |
| Best for | Small integer range | k close to n |
Step by step
| Step | What happens |
|---|---|
| 1 | Find the maximum value to size the count array. |
| 2 | Count how many times each value occurs. |
| 3 | (Optional) Convert counts to prefix sums for stability. |
| 4 | Write each value into the output the number of times it appears. |
| 5 | The output array is now fully sorted. |
Worked example
Sorting [1, 4, 1, 2, 4] (values range from 0 to 4, so the count array has 5 slots):
| Pass | State | Action |
|---|---|---|
| Scan input | count = [0, 2, 1, 0, 2] | Tally occurrences: 1 appears twice, 2 once, 4 twice. |
| Prefix sums | count = [0, 2, 3, 3, 5] | Each slot now holds how many values are <= its index, giving final positions. |
Place 4 | output = [_, _, _, _, 4] | Read right-to-left: count[4] = 5, so 4 goes to index 4; decrement to 4. |
Place 2 | output = [_, _, 2, _, 4] | count[2] = 3, so 2 goes to index 2; decrement to 2. |
Place 1 | output = [_, 1, 2, _, 4] | count[1] = 2, so 1 goes to index 1; decrement to 1. |
Place 4 | output = [_, 1, 2, 4, 4] | count[4] = 4, so this 4 goes to index 3; decrement to 3. |
Place 1 | output = [1, 1, 2, 4, 4] | count[1] = 1, so this 1 goes to index 0. Array is sorted. |
When to use counting sort
| Use it when | Avoid it when |
|---|---|
| You sort integers (or keys mappable to integers) in a small, known range. | The value range k is far larger than the element count n. |
You need linear O(n + k) time and can afford the extra arrays. | Memory is tight - the count array costs O(k) regardless of n. |
| You need a stable sort as a subroutine (e.g. inside radix sort). | Keys are floats, strings, or arbitrary objects with no integer mapping. |
| The maximum value is bounded and cheap to compute up front. | The range is unknown or unbounded, so you cannot size the count array. |
Counting Sort code
A clean, runnable Counting Sort implementation in Python, JavaScript, Java, C++, C. Pick a language, copy the code, or open it pre-loaded in the Coddy Playground.
Counting Sort code in Python
Python
1def counting_sort(a):2 # Works for non-negative integers with a small max value3 counts = [0] * (max(a) + 1)4 for value in a:5 counts[value] += 16 # Prefix sums turn counts into final positions7 for i in range(1, len(counts)):8 counts[i] += counts[i - 1]9 out = [0] * len(a)10 for value in reversed(a): # reversed keeps equal values stable11 counts[value] -= 112 out[counts[value]] = value13 return out14
15
16nums = [4, 2, 2, 8, 3, 3, 1]17print("Before:", nums)18print("After: ", counting_sort(nums))Counting Sort code in JavaScript
JavaScript
1function countingSort(arr) {2 // Count occurrences of each value, then rebuild in order3 const max = Math.max(...arr);4 const count = new Array(max + 1).fill(0);5 for (const x of arr) count[x]++;6 const out = [];7 count.forEach((c, value) => {8 for (let k = 0; k < c; k++) out.push(value);9 });10 return out;11}12
13const data = [4, 2, 9, 2, 7, 4, 1, 4];14console.log("Before:", data);15console.log("Sorted:", countingSort(data));Counting Sort code in Java
Java
1import java.util.Arrays;2
3public class Main {4 static int[] countingSort(int[] arr) {5 int max = 0;6 for (int v : arr) max = Math.max(max, v);7 int[] count = new int[max + 1];8 for (int v : arr) count[v]++;9 // Prefix sums turn counts into final positions10 for (int i = 1; i <= max; i++) count[i] += count[i - 1];11 int[] out = new int[arr.length];12 // Walk backwards so equal values keep their order (stable)13 for (int i = arr.length - 1; i >= 0; i--) {14 out[--count[arr[i]]] = arr[i];15 }16 return out;17 }18
19 public static void main(String[] args) {20 int[] arr = {4, 2, 2, 8, 3, 3, 1};21 System.out.println("Before: " + Arrays.toString(arr));22 int[] sorted = countingSort(arr);23 System.out.println("After: " + Arrays.toString(sorted));24 }25}Counting Sort code in C++
C++
1#include <algorithm>2#include <iostream>3#include <vector>4
5void printVec(const std::vector<int>& a) {6 for (int x : a) std::cout << x << " ";7 std::cout << "\n";8}9
10void countingSort(std::vector<int>& a) {11 if (a.empty()) return;12 int maxVal = *std::max_element(a.begin(), a.end());13 // count[v] = how many times v appears14 std::vector<int> count(maxVal + 1, 0);15 for (int x : a) ++count[x];16 // Rebuild the array from the counts17 size_t idx = 0;18 for (int v = 0; v <= maxVal; ++v) {19 while (count[v]-- > 0) a[idx++] = v;20 }21}22
23int main() {24 std::vector<int> data = {4, 2, 2, 8, 3, 3, 1, 7};25 std::cout << "Before: ";26 printVec(data);27 countingSort(data);28 std::cout << "After: ";29 printVec(data);30 return 0;31}Counting Sort code in C
C
1#include <stdio.h>2#include <stdlib.h>3
4void printArr(const int a[], int n) {5 for (int i = 0; i < n; i++) printf("%d ", a[i]);6 printf("\n");7}8
9void countingSort(int a[], int n) {10 int maxVal = a[0];11 for (int i = 1; i < n; i++) {12 if (a[i] > maxVal) maxVal = a[i];13 }14 // count[v] = how many times v appears15 int* count = calloc(maxVal + 1, sizeof(int));16 for (int i = 0; i < n; i++) count[a[i]]++;17 // Rebuild the array from the counts18 int idx = 0;19 for (int v = 0; v <= maxVal; v++) {20 while (count[v]-- > 0) a[idx++] = v;21 }22 free(count);23}24
25int main(void) {26 int data[] = {4, 2, 2, 8, 3, 3, 1, 7};27 int n = sizeof(data) / sizeof(data[0]);28 printf("Before: ");29 printArr(data, n);30 countingSort(data, n);31 printf("After: ");32 printArr(data, n);33 return 0;34}Counting Sort FAQ
What is the time complexity of counting sort?
Counting sort is
O(n + k), where n is the number of elements and k is the range of possible values. When k = O(n) this is linear time. It uses O(n + k) extra space.Is counting sort stable?
It can be. The stable version builds prefix sums of the counts and places elements from right to left, which preserves the relative order of equal keys. The simple "rewrite by value" version shown here produces a correct sort but is used mainly for plain integers.
When should I use counting sort?
Use it when sorting integers (or keys mappable to integers) within a small, known range. If the value range
k is much larger than the number of elements, the count array wastes memory and a comparison sort is better.What is the difference between counting sort and radix sort?
Counting sort sorts by the whole value in one pass and needs a count array as large as the value range. Radix sort sorts digit by digit and usually calls a stable counting sort on each digit, which keeps the per-pass range small (e.g.
10 for decimal digits). Radix sort handles large value ranges that would make a single counting sort impractical.Why is counting sort not always faster than quicksort?
Counting sort is
O(n + k), so it only wins when the value range k is comparable to n. If k is huge - say sorting 100 values in the range 0 to 1,000,000,000 - the O(k) count array dominates and wastes memory, while an O(n log n) comparison sort like quicksort stays fast and space-efficient.Can counting sort handle negative numbers?
Yes, with a small offset. Instead of indexing the count array by the value directly, index it by
value - min, so the smallest value maps to index 0. The count array size becomes max - min + 1. Forgetting this offset is a common bug that crashes on negative inputs.Related resources
More visualizations
