Counting sort in Java

The Java implementation of unstable version

The implementation in Java is presented below.

public static int[] countingSort(int[] numbers) {

    int maxVal = 10; // we suppose the maximum is 10
    int k = maxVal + 1; // the length of the array containing counts
    int[] counts = new int[k]; // it stores 11 zeros with indexes from 0 to k-1

    /* in this loop we count distinct numbers in the input array */
    for (int i = 0; i < numbers.length; i++) {
        counts[numbers[i]]++;
    }

    int pos = 0; // a position in the numbers array

    /* in this loop we modify the input array to make it sorted */
    for (int num = 0; num < k; num++) { // get the next element
        int count = counts[num]; // get the count of the element
        while (count > 0) {
            numbers[pos] = num; // write it in the numbers array
                pos++;
                count--;
            }
    }

    return numbers;
}

We assumed that the maximum element is 10, but in fact, the best strategy can be to pass the possible maximum as a parameter to the method or to determine it by traversing the input array with the time complexity O(n).

Let's sort the same array.

countingSort(new int[] {2, 0, 3, 5, 0, 3, 3, 1}); // [0, 0, 1, 2, 3, 3, 3, 5]

As you can see, it can sort number arrays.

The stable counting sort

This algorithm also can be stable that may be required when sorting keys. To make it stable we will calculate cumulative counts.

public static int[] stableCountingSort(int[] numbers, int max) {

    int k = max + 1; // the length of the array containing counts
    int[] counts = new int[k]; // it stores counts with indexes from 0 to k-1

    for (int i = 0; i < numbers.length; i++) {
        counts[numbers[i]]++;
    }

    for (int i = 1; i < counts.length; i++) {
        counts[i] = counts[i - 1] + counts[i]; // cumulative counts
    }

    int[] sortedNumbers = new int[numbers.length];

    for (int i = numbers.length - 1; i >= 0; i--) {  // go through input array in backward
        int rightmostIndex = counts[numbers[i]] - 1; // get the rightmost index
        sortedNumbers[rightmostIndex] = numbers[i];
        counts[numbers[i]]--; // decrease the index to calculate the previous occurrence
    }

    return sortedNumbers;
}

stableCountingSort(new int[] {2, 0, 3, 5, 0, 3, 3, 1}, 10); // [0, 0, 1, 2, 3, 3, 3, 5]