Hi,

This blog is to help you to understand counting sort in easiest manner, counting sort can sort the range in linear time but we have to provide the starting element and last highest element of the range (means elements in the range should be greater then or equal to starting point and should be less then or equal to limit value), extra space will be taken of order of the size of the range.

               In Counting sort we maintain a count for each element inside our range and create a sorted range on the basis of it. Lets make it more simpler.

For example

Let we have our range is 2, 1, 2, 4, 0, 3, 1, 5

int[] arr = new  int[] { 2, 1, 2, 4, 0, 3, 1, 5};

we need an extra space to store the occurrence of every element inside the array (occurrence of 0, 1, 2, 3, 4, 5 has to be counted) so we need space of size 6 units.

int[] count = new int[6];

now we need to count the frequency of every element of the range and put it inside the count array.

arr     2 1 2 4 0 3 1 5

count   1 2 2 1 1 1

index   0 1 2 3 4 5

now we need to modify our count array such that in the updated array element at index i will be sum of itself and the element before it. for 1<= i < n-1.

arr[ i ] = arr[ i ] + arr[ i - 1 ]

now our count will be 

count   1 3 5 6 7 8

now from this count array we will generate our sorted array by following these steps

we need to create a new array for the output of the size of the input range.

int[] output = new int[8];

traverse the elements of the input range and find the frequency of it. (first element is 2  considering it as index value for which we have count array value 5 )

at index count[2] - 1 ( 5 - 1 ) in output array we need to put our traversed value then reduce count value of it by 1.

arr     2 1 2 4 0 3 1 5

count   1 3 5 6 7 8

index   0 1 2 3 4 5

output  0 0 0 0 2 0 0 0 

after reducing the count value by 1

count   1 3 4 6 7 8

Next element inside input is 1

at index count[1] - 1  ( 3 - 1 ) in output array we need to put our traversed value then reduce count value of it by 1.

arr     2 1 2 4 0 3 1 5

count   1 3 4 6 7 8

index   0 1 2 3 4 5

output  0 0 1 0 2 0 0 0 

after reducing the count value by 1

count   1 2 4 6 7 8

Next element inside input is 2

at index count[2] - 1  ( 4 - 1 ) in output array we need to put our traversed value then reduce count value of it by 1.

arr     2 1 2 4 0 3 1 5

count   1 2 4 6 7 8

index   0 1 2 3 4 5

output  0 0 1 2 2 0 0 0 

after reducing the count value by 1

count   1 2 3 6 7 8

Next element inside input is 4

at index count[4] - 1  ( 7 - 1 ) in output array we need to put our traversed value then reduce count value of it by 1.

arr     2 1 2 4 0 3 1 5

count   1 2 3 6 7 8

index   0 1 2 3 4 5

output  0 0 1 2 2 0 4 0 

after reducing the count value by 1

count   1 2 3 6 6 8

Next element inside input is 0

at index count[0] - 1  ( 1 - 1 ) in output array we need to put our traversed value then reduce count value of it by 1.

arr     2 1 2 4 0 3 1 5

count   1 2 3 6 6 8

index   0 1 2 3 4 5

output  0 0 1 2 2 0 4 0

after reducing the count value by 1

count   0 2 3 6 6 8

Next element inside input is 3

at index count[3] - 1  ( 6 - 1 ) in output array we need to put our traversed value then reduce count value of it by 1.

arr     2 1 2 4 0 3 1 5

count   0 2 3 6 6 8

index   0 1 2 3 4 5

output  0 0 1 2 2 3 4 0 

after reducing the count value by 1

count   0 2 3 5 6 8

Next element inside input is 1

at index count[1] - 1  ( 2 - 1 ) in output array we need to put our traversed value then reduce count value of it by 1.

arr     2 1 2 4 0 3 1 5

count   0 2 3 5 6 8

index   0 1 2 3 4 5

output  0 1 1 2 2 3 4 0 

after reducing the count value by 1

count   0 1 3 5 6 8

Next element inside input is 5

at index count[5] - 1  ( 8 - 1 ) in output array we need to put our traversed value then reduce count value of it by 1.

arr     2 1 2 4 0 3 1 5

count   0 1 3 5 6 8

index   0 1 2 3 4 5

output  0 1 1 2 2 3 4 5 

after reducing the count value by 1

count   0 1 3 5 6 7

Program for Count sort 

public class CountSort {
	public static void main(String[] args) {
		// We considered our range from 0 to 9 in this case
		int[] arr = new int[] { 1, 4, 1, 2, 7, 5, 2 };
		int[] count = new int[10];
		int[] output = new int[arr.length];

		System.out.print("Input array : ");
		for (int i : arr)
			System.out.print(i + " ");
		System.out.println();

		//stroring the count of elements inside the input array
		for (int i : arr)
			count[i]++;

		//adding previous index value in the new updated count array
		for (int i = 1; i < 10; i++)
			count[i] += count[i - 1];

		//puting values in output array
		for (int i : arr) {
			output[count[i]-1] = i;
	        --count[i];
		}

		System.out.print("Output array: ");
		for (int i : output)
			System.out.print(i + " ");
		System.out.println();

	}
}

Output of the above program is

Input array : 1 4 1 2 7 5 2 
Output array: 1 1 2 2 4 5 7 

Thanks :)