How to perform counting sort in Java?

To perform a counting sort in Java, you can use an array to count the frequency of each element in the input array, and then use this count array to create a sorted array.

Here is an example of how you can perform a counting sort in Java:

public static int[] countingSort(int[] array, int maxValue) {
    int[] count = new int[maxValue + 1];
    int[] sortedArray = new int[array.length];
    
    for (int i = 0; i < array.length; i++) {
        count[array[i]]++;
    }
    
    for (int i = 1; i < count.length; i++) {
        count[i] += count[i - 1];
    }
    
    for (int i = array.length - 1; i >= 0; i--) {
        sortedArray[count[array[i]] - 1] = array[i];
        count[array[i]]--;
    }
    
    return sortedArray;
}

In this example, the countingSort method takes an integer array and the maximum value in the array as arguments, and returns a sorted array. The method first initializes the count array and the sorted array, and then it counts the frequency of each element in the input array using a loop.

Next, the method sums the count array so that each element stores the number of elements that are less than or equal to it. Finally, the method iterates through the input array in reverse order and fills the sorted array using the count array.

The counting sort algorithm has a time complexity of O(n), where n is the number of elements in the input array, and it requires O(k) additional space, where k is the range of the input values. This makes counting sort an efficient sorting algorithm for arrays with small or fixed ranges of values.

Keep in mind that this is just one way to perform a counting sort in Java. You can use different techniques and optimization strategies to achieve the same result, such as using the Arrays.sort method of the java.util package, or using other sorting algorithms such as quicksort or mergesort.