[Algorithms] Counting Sort

All Comparison Sort should take at least O(nlgn) time.

Counting Sort skip the comparison and improve the sorting time to O(n).
There will be extra space O(k) where k is the range of the array to be sorted.

import java.util.Arrays;
 
public static void countingSort(int[] a, int low, int high)
{
    int[] counts = new int[high - low + 1];  

    // this will hold all possible values, from low to high
    for (int x : a)
        counts[x - low]++;  

        // x is some value in array, counts[x - low] stores how many time x appears.
 
    int current = 0;
    for (int i = 0; i < counts.length; i++)
    {
        Arrays.fill(a, current, current + counts[i], i + low);  

        // counts[i] stores how many times i + low appears

        // we should fill counts[i] elements with this value: i + low
        current += counts[i];

        // leap forward by counts[i] steps
    }
}