Counting Sort

Sorting without comparing elements

Counting sort approaches the problem differently: instead of asking “which of two elements is smaller?” it counts how many times each value occurs. This is possible when the values are integers from a reasonably small known range.

static void countingSort(int[] a, int maxValue) {
    int[] count = new int[maxValue + 1];

    for (int value : a) {
        count[value]++;
    }

    int index = 0;
    for (int value = 0; value < count.length; value++) {
        for (int c = 0; c < count[value]; c++) {
            a[index++] = value;
        }
    }
}

The count array stores frequencies. If count[4] == 3, the value 4 must be written to the result three times. The counters are scanned from smaller indexes to larger ones, so the final array is automatically produced in sorted order.

Complexity depends on the range

Let n be the number of elements and k the size of the possible-value range. The running time is then O(n + k), while extra space is O(k). When k is small, this can be faster than comparison-based sorting.

When the idea stops being useful

If an array contains only a few elements but possible values range from zero to billions, creating a huge counter array makes no sense. Counting sort is advantageous specifically when the value range is compact enough relative to the amount of data.