Counting Sort

Counting sort is like tallying how many of each number there are on a scoreboard and then reading the tallies out in order, with no comparing.

In this page:

Basic Idea
Step by Step
Small Array
Practice
Summary

Syntax

markup

count = [0] * (max_value + 1)
for x in arr:
    count[x] += 1
result = []
for value in range(len(count)):
    result.extend([value] * count[value])

Basic Idea

Counting sort avoids comparisons entirely: it counts how many times each distinct value appears, then uses those counts to place every value directly into its correct sorted position — it only works when values fall within a small, known range of integers.

Example: Basic Idea

#include <iostream>
using namespace std;
int main() {
	int arr[] = {4, 2, 2, 8, 3, 3, 1};
	int n = 7, maxVal = 8;
	int count[9] = {0};
	for (int i = 0; i < n; i++) count[arr[i]]++;
	for (int i = 0; i <= maxVal; i++)
		for (int j = 0; j < count[i]; j++) cout << i << " ";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int[] arr = {4, 2, 2, 8, 3, 3, 1};
		int maxVal = 8;
		int[] count = new int[9];
		for (int x : arr) count[x]++;
		for (int i = 0; i <= maxVal; i++)
			for (int j = 0; j < count[i]; j++) System.out.print(i + " ");
	}
}

arr = [4, 2, 2, 8, 3, 3, 1]
max_val = 8
count = [0] * (max_val + 1)
for x in arr:
    count[x] += 1
result = []
for i, c in enumerate(count):
    result += [i] * c
print(result)

#include <stdio.h>
int main() {
	int arr[] = {4, 2, 2, 8, 3, 3, 1};
	int n = 7, maxVal = 8;
	int count[9] = {0};
	for (int i = 0; i < n; i++) count[arr[i]]++;
	for (int i = 0; i <= maxVal; i++)
		for (int j = 0; j < count[i]; j++) printf("%d ", i);
	return 0;
}

Step by Step

The algorithm builds a count array indexed by value, tallies occurrences with one pass over the input, then converts those counts into starting positions (via a running total) so each value can be placed directly into the output array without comparing it to anything.

Example: Step by Step

#include <iostream>
using namespace std;
int main() {
	cout << "Tally occurrences into count[], convert counts to prefix-sum start positions, then place each value";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Tally occurrences into count[], convert counts to prefix-sum start positions, then place each value");
	}
}

print("Tally occurrences into count[], convert counts to prefix-sum start positions, then place each value")

#include <stdio.h>
int main() {
	printf("Tally occurrences into count[], convert counts to prefix-sum start positions, then place each value");
	return 0;
}

Small Array

Tracing counting sort on a small array of small integers like [4, 2, 2, 8, 3, 3, 1] shows how the count array fills in, then how those counts translate into exact output positions for each value.

Example: Small Array

#include <iostream>
using namespace std;
int main() {
	int arr[] = {4, 2, 2, 8, 3, 3, 1};
	int count[9] = {0};
	for (int i = 0; i < 7; i++) count[arr[i]]++;
	for (int i = 0; i <= 8; i++) if (count[i] > 0) cout << "value " << i << " occurs " << count[i] << " times" << endl;
	return 0;
}

public class Main {
	public static void main(String[] args) {
		int[] arr = {4, 2, 2, 8, 3, 3, 1};
		int[] count = new int[9];
		for (int x : arr) count[x]++;
		for (int i = 0; i <= 8; i++) if (count[i] > 0) System.out.println("value " + i + " occurs " + count[i] + " times");
	}
}

arr = [4, 2, 2, 8, 3, 3, 1]
count = [0] * 9
for x in arr:
    count[x] += 1
for i, c in enumerate(count):
    if c > 0:
        print("value", i, "occurs", c, "times")

#include <stdio.h>
int main() {
	int arr[] = {4, 2, 2, 8, 3, 3, 1};
	int count[9] = {0};
	for (int i = 0; i < 7; i++) count[arr[i]]++;
	for (int i = 0; i <= 8; i++) if (count[i] > 0) printf("value %d occurs %d times\n", i, count[i]);
	return 0;
}

Practice

Try counting sort on an array with a wide range of values compared to one with a narrow range — a huge range wastes a lot of space and time building an oversized count array even for a small input, which is exactly its main limitation.

Example: Practice

#include <iostream>
using namespace std;
int main() {
	cout << "A narrow value range makes counting sort very fast; a huge range wastes space and time";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("A narrow value range makes counting sort very fast; a huge range wastes space and time");
	}
}

print("A narrow value range makes counting sort very fast; a huge range wastes space and time")

#include <stdio.h>
int main() {
	printf("A narrow value range makes counting sort very fast; a huge range wastes space and time");
	return 0;
}

Summary

Counting sort runs in O(n + k) time and space, where k is the range of possible values — this beats comparison-based sorts' O(n log n) lower bound, but only because it sidesteps comparisons entirely, at the cost of needing that range to be small and known in advance.

Example: Summary

#include <iostream>
using namespace std;
int main() {
	cout << "Counting sort: O(n + k) time and space, where k is the range of values, beating O(n log n)";
	return 0;
}

public class Main {
	public static void main(String[] args) {
		System.out.println("Counting sort: O(n + k) time and space, where k is the range of values, beating O(n log n)");
	}
}

print("Counting sort: O(n + k) time and space, where k is the range of values, beating O(n log n)")

#include <stdio.h>
int main() {
	printf("Counting sort: O(n + k) time and space, where k is the range of values, beating O(n log n)");
	return 0;
}

Chapter Quiz — Complete all 9 topics to unlock

0/9 topics done

Complete these topics first:

← Previous Lesson Heap Sort Next Lesson → Radix Sort