Counting sort
›Short versionOpen if you only have a minute.
- Count how often each non-negative integer appears, turn the counts into end positions, and write each value into an output array.
- Writing from the right end of the input makes this version stable. Equal keys leave in their original order.
- It allocates a count array of length k + 1 and an output array of length n. Extra memory is O(n + k). The input is copied back at the end.
- Time is O(n + k) on every input, and that is the worst case too. A huge key range costs more than the comparisons in Arrays.sort.
- Use it for dense non-negative integers, including the digit pass inside radix sort. General data goes to Arrays.sort: Timsort for objects, dual-pivot quicksort for primitives.
Positions come from counts
The algorithm never compares two keys to decide which is smaller. It uses the key as an index. After the first loop, count[v] is how many times v occurs. The prefix-sum loop replaces that with how many keys are less than or equal to v. That number is the end position of v in the output: the last v belongs at index count[v] - 1.
On [4, 2, 2, 1] the raw counts are one 1, two 2s, and one 4. After the prefix sums, those end positions are 1, 3, and 4. The input is then placed from right to left, and each placement decrements the next open slot for that key.
Stable, and the range is the memory
This placement is a . A left-to-right scan with the same prefix sums fills the last slot first and reverses equal keys. The direction of the scan is the whole difference.
The sort needs a second array of length n and a count array of length k + 1, where k is the largest key. That is . Time matches that shape: one pass over the input, one pass over the key range, one placement pass. Best and worst case are both O(n + k). When k is close to n, that is linear. When the keys are sparse, the count array dominates.
Five keys are drawn from 0 through 1,000,000. Which allocation dominates the running time?
The count array of about a million slots. Building the prefix sums walks that whole range. The five elements are the cheap part. A comparison sort of five ints does not allocate a table sized to the largest key.
When the library sort takes over
Counting sort fits scores, small ids, and other dense non-negative integers whose range you can afford to allocate. For a general array, call Arrays.sort. Objects are sorted with . An int[] is sorted with a dual-pivot quicksort, which stays fast when the integers span the whole int range. Counting sort remains the right subroutine when a later algorithm, such as radix sort, needs a stable pass over a digit from 0 to 9.
public class CountingSort {
static void sort(int[] arr) {
if (arr.length == 0) {
return;
}
int max = 0;
for (int value : arr) {
if (value < 0) {
throw new IllegalArgumentException("counting sort expects non-negative keys");
}
if (value > max) {
max = value;
}
}
if (max == Integer.MAX_VALUE) {
throw new IllegalArgumentException("key range does not fit in a count array");
}
int[] count = new int[max + 1];
for (int value : arr) {
count[value]++;
}
for (int value = 1; value <= max; value++) {
count[value] += count[value - 1];
}
int[] output = new int[arr.length];
for (int i = arr.length - 1; i >= 0; i--) {
int value = arr[i];
output[count[value] - 1] = value;
count[value]--;
}
System.arraycopy(output, 0, arr, 0, arr.length);
}
public static void main(String[] args) {
int[] arr = {4, 2, 2, 8, 3, 3, 1};
sort(arr);
for (int value : arr) {
System.out.print(value + " ");
}
System.out.println();
}
}