Java Counting Sort for Linear Time Integer Sorting

Introduction

Counting sort java developers use it when they need to sort integers in linear time, faster than the O(n log n) lower bound that every comparison sort must respect. The algorithm was first published by Harold H. Seward in 1954 in his MIT master's thesis "Information Sorting in the Application of Electronic Computers to Business Operations", where he introduced both counting sort and radix sort to handle punch card data efficiently. The idea was refined by Donald Knuth in The Art of Computer Programming Volume 3 (1973), who gave the cleanest analysis of the running time as O(n + k) where n is the number of items and k is the size of the key range.

For a Java learner, counting sort java is the gateway to understanding why some sorts beat the comparison lower bound. By trading comparison for counting, we trade O(n log n) for O(n + k), which is linear whenever the key range k is O(n). The trick is also the foundation of radix sort, which uses counting sort as a stable subroutine on each digit. Building counting sort from scratch teaches the link between counting, prefix sums, and stable placement, which appears again in histograms, cumulative distribution tables, and the radix sort you will see in the next post.

What is Counting Sort?

Counting sort is a non comparison, integer key sort that runs in O(n + k) time and O(k) auxiliary memory, where n is the number of input items and k is the range of the input keys. It belongs to the distribution sort family, alongside radix sort and bucket sort, all of which exploit the structure of the keys themselves instead of comparing them pairwise. Unlike quick sort or merge sort, counting sort never compares two keys, so it sidesteps the O(n log n) comparison lower bound proven by Fredman in 1976.

Counting sort is stable, meaning two items with the same key appear in the output in the same order they appeared in the input. Stability matters because it lets us sort by one key and then sort again by another key without losing the first ordering. Radix sort exploits this by running counting sort digit by digit from least significant to most significant. The catch is that counting sort only works when keys are small non negative integers. If the keys are floating point numbers or strings, you must first transform them into bounded integer keys.

How Counting Sort Works - Step by Step

Step 1: Find the key range. Scan the input array to find the minimum and maximum key. The range k is max minus min plus 1. For an input of 4, 2, 2, 8, 3, 3, 1 the minimum is 1 and the maximum is 8, so k equals 8. If the keys are not already non negative, subtract the minimum to shift them into the range 0 to k minus 1.

Step 2: Build the count array. Create an integer array count of size k, all initialised to zero. Walk through the input once, and for each key, increment the count at index key minus min. After this pass, count[i] holds the number of input items with key equal to i plus min. For the example above, count becomes 1, 2, 2, 0, 0, 0, 0, 1 for keys 1 through 8.

Step 3: Convert counts to prefix sums. Walk the count array from index 0 to k minus 1, and replace each count[i] with the running sum so far. After this pass, count[i] holds the number of input items with key less than or equal to i plus min. The prefix sum tells us the final position of each key: items with key value v will occupy output positions count[v] minus 1 down to count[v minus 1]. For our example, count becomes 1, 3, 5, 5, 5, 5, 5, 6.

Step 4: Build the output array by walking the input backwards. For each input item, look up its key, find its current prefix sum at count[key minus min], decrement that prefix sum, and place the item at that position in the output. Walking backwards preserves stability: items with the same key appear in the output in the same relative order they had in the input.

Step 5: Copy the output back. If you need to sort the input in place, copy the output array back to the input array. Otherwise, return the output array as a new sorted array.

Java Program for Counting Sort

public class CountingSortDemo {

    // Sorts an array of non negative integers using counting sort.
    // Returns a new sorted array. The input array is not modified.
    public static int[] countingSort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return new int[0];
        }

        // Step 1: find the key range.
        int min = arr[0];
        int max = arr[0];
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] < min) {
                min = arr[i];
            }
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        int k = max - min + 1;

        // Step 2: build the count array by frequency.
        int[] count = new int[k];
        for (int i = 0; i < arr.length; i++) {
            count[arr[i] - min]++;
        }

        // Step 3: convert counts to prefix sums.
        // count[i] now holds the number of items with key <= (i + min).
        for (int i = 1; i < k; i++) {
            count[i] += count[i - 1];
        }

        // Step 4: walk the input backwards and place each item.
        // Walking backwards preserves stability for equal keys.
        int[] output = new int[arr.length];
        for (int i = arr.length - 1; i >= 0; i--) {
            int key = arr[i] - min;
            count[key]--;
            output[count[key]] = arr[i];
        }

        return output;
    }

    public static void main(String[] args) {
        int[] data = {4, 2, 2, 8, 3, 3, 1};

        System.out.print("Input:  ");
        for (int v : data) {
            System.out.print(v + " ");
        }
        System.out.println();

        int[] sorted = countingSort(data);

        System.out.print("Output: ");
        for (int v : sorted) {
            System.out.print(v + " ");
        }
        System.out.println();
    }
}

Code Explanation - Line by Line

The method starts with a defensive check for null or empty input and returns an empty array immediately. This handles the edge cases that often cause NullPointerException or array index out of bounds in less careful implementations.

The first loop finds the minimum and maximum key in a single pass. Both the minimum and the maximum are tracked together so the loop only walks the array once. We need the minimum because the algorithm supports negative keys by shifting them so the smallest key maps to index 0 in the count array.

The count array is allocated with size k, which is max minus min plus 1. Each slot in count holds the frequency of one specific key value. The second loop walks the input and increments count[arr[i] minus min] for each item. After this loop, count[i] is the number of items whose key equals i plus min.

The third loop converts the frequency array into a prefix sum array. After this loop, count[i] is the number of items whose key is less than or equal to i plus min. This is the magic step: the prefix sum directly tells us the end position of each key group in the output.

The fourth loop walks the input backwards. For each item, we read its key, decrement the prefix sum at that key, and place the item at the resulting position. Walking backwards is essential for stability: when two items have the same key, the one that appeared later in the input is placed later in the prefix sum update, so it ends up in the higher output position, preserving the original relative order.

Sample Input and Output

Input:  4 2 2 8 3 3 1
Output: 1 2 2 3 3 4 8

The output is the sorted version of the input, with both occurrences of 2 and both occurrences of 3 placed before 4 and 8. The order of equal keys matches the input order, which is what stable means in practice. The algorithm touches each element a constant number of times across the four passes, which is why the running time is O(n + k).

Common Mistakes to Avoid

First, do not allocate the count array of size max without subtracting the minimum. If the input has negative keys, the shift is essential or you will get a negative array index. Even with non negative keys, if the minimum is large and the range is small, allocating an array of size max wastes memory. Always use max minus min plus 1.

Second, do not walk the input forwards when placing items into the output. Walking forwards breaks stability, because the first occurrence of a duplicate key gets the higher prefix sum first and ends up after the later occurrence. Always walk backwards.

Third, do not forget to decrement the prefix sum before placing the item. The prefix sum at count[key] is the number of items with key less than or equal to key, which is one past the last position for that key group. You must decrement to get the next free position.

Fourth, do not use counting sort for keys with a huge range. If the keys are sparse 32 bit integers, the count array would be 4 billion slots. For such inputs, use radix sort, which runs counting sort on each digit with a range of 10 or 256.

Real-World Applications

Counting sort powers the first pass of every radix sort implementation. The java.util.Arrays.sort(int[]) method in the JDK uses a dual pivot quick sort, not counting sort, because it cannot assume the key range is small. However, the JDK uses counting sort internally for sorting chars in some string utilities where the key range is bounded by 65536.

Histograms in image processing use counting sort logic to compute intensity distributions, because pixel values are bounded by 255 for grayscale and 255 per channel for colour. Database query planners use counting sort on small enum columns, where the cardinality is known at compile time.

In competitive programming, counting sort is the standard tool for problems that involve frequencies of small integers, such as finding the mode of an array of exam scores or counting inversions in a permutation of 1 to n. The algorithm is also the engine behind the suffix array construction in some linear time text indexing algorithms, where the alphabet is small and bounded.

Conclusion

We built counting sort from scratch and saw why it runs in O(n + k) time instead of the O(n log n) comparison lower bound. We learned that stability comes from walking the input backwards, that the prefix sum converts frequencies into final positions, and that the key range k determines whether counting sort is practical. Next, study radix sort, which chains counting sort across multiple digits to handle huge key ranges, and bucket sort, which generalises counting sort to floating point keys.