Counting Sort in Java
Problem
Counting sort is a non-comparison sort: when values fall in a small known range, it counts how many times each value occurs and rebuilds the array from those counts.
Given an array of non-negative integers with a small maximum value, sort it in ascending order using counting sort.
Java Program
import java.util.Arrays;
public class CountingSort {
public static void main(String[] args) {
int[] arr = {4, 1, 3, 4, 0, 2, 1, 3};
int max = Arrays.stream(arr).max().getAsInt();
int[] count = new int[max + 1]; // one tally slot per possible value
for (int value : arr) {
count[value]++;
}
int index = 0;
for (int value = 0; value <= max; value++) {
while (count[value]-- > 0) {
arr[index++] = value; // write each value back as many times as it was seen
}
}
System.out.println(Arrays.toString(arr));
}
}Output
Core Logic
Instead of comparing elements, each value is used directly as an index into a tally array; reading the tallies in index order produces the values in sorted order.
- 1The largest value,
max, sets the size ofcount, giving one slot for every value from 0 to max. - 2One pass over the array increments
count[value]for each element. - 3A second pass walks
valuefrom 0 to max and writes that value backcount[value]times. - 4
indextracks the next position to fill, so the array is overwritten in sorted order.
count = [1, 2, 1, 2, 2], so the rebuild writes one 0, two 1s, one 2, two 3s and two 4s.Key Point: Counting sort beats O(n log n) only when the value range k is small — sorting a handful of numbers that go up to a million would allocate a million-slot array for nothing.
Why: One pass counts the n elements and another walks the k possible values; the tally array needs one slot per possible value.
Key Concepts
Approach 2: Stable Version (Supports Negatives)
import java.util.Arrays;
public class CountingSortStable {
public static void main(String[] args) {
int[] arr = {3, -2, 5, 0, -2, 4, 3};
int min = Arrays.stream(arr).min().getAsInt();
int max = Arrays.stream(arr).max().getAsInt();
int[] count = new int[max - min + 1]; // offset by min, so negatives get a slot too
for (int value : arr) {
count[value - min]++;
}
for (int i = 1; i < count.length; i++) {
count[i] += count[i - 1]; // count[i] now = how many values are <= this one
}
int[] sorted = new int[arr.length];
for (int i = arr.length - 1; i >= 0; i--) { // walk backwards to keep equal values in order
sorted[--count[arr[i] - min]] = arr[i];
}
System.out.println(Arrays.toString(sorted));
}
}
Output
Core Logic
Turning the tallies into running totals tells each value exactly where its last copy belongs, which allows a stable placement — and shifting every value by the minimum makes room for negative numbers.
- 1
minandmaxsize the tally array tomax - min + 1, and each value is stored at indexvalue - min. - 2After counting,
count[i] += count[i - 1]converts tallies into prefix sums: the number of values less than or equal to each value. - 3The input is walked from right to left, and each value is placed at
--count[value - min]in a newsortedarray. - 4Walking backwards means the last copy of a value takes the last slot, so equal values keep their original relative order.
[3, -2, 5, 0, -2, 4, 3], min is -2, so -2 maps to index 0 and 5 maps to index 7 of an 8-slot tally array.Key Point: This stable form is the one radix sort relies on, and it works on records sorted by an integer key — not just bare numbers — because elements are moved, not regenerated.
Why: Counting, the prefix-sum pass and the placement pass are each linear, and the output array adds n slots to the k-slot tally array.
Key Concepts
Interview Questions
When is counting sort a good choice?
When the values are integers in a small, known range, such as exam marks or ages. A huge range makes the count array impractical.
Can counting sort handle negative numbers?
Yes, by offsetting every value by the minimum, so the smallest value maps to index 0 — as the stable version on this page does.