Counting sort also called an integer sorting algorithm. Counting sort algorithm is based on keys in a specific range. It counts the number of items for distinct key value, use these keys to determine position or indexing on the array and store respective counts for each key. Finally, sort values based on keys and make sequences the repetition of key based on counts.

Counting sort is suitable where variation in keys are is not significantly greater than the number of items. Its running time is linear as numbers of items(n)+difference between max and min key values.

Points to Remember

• Data structure: Array
• Worst-case performance: O(n+k), where k is the range of the non-negative key values.
• Worst-case space complexity: O(n+k)

Advantage

• Counting sort is a stable sort, where if two items have the same key, they should have the same relative position in the sorted output as they did in the input.

Disadvantage

• Data range should be predefined, if not then addition loops required to get min and max value to get range.
• Not much variation on key values otherwise will occupy unnecessary space in the array.

Steps for Counting Sort

For easily understand, consider the data in the range 0 to 9 for below example:
Input data: 2, 6, 3, 2, 8, 4, 8, 1, 5, 3, 1, 4, 0
1) Create an array of size 10 (index values 0-9) and store the count of each 
   unique item.
  Index:     0  1  2  3  4  5  6  7  8  9
  Count:     1  2  2  2  2  1  1  0  2  0

2) Execute loop for each index for array and check counts are more than zero. 
   repeat the index/key value until count reach to zero. Store these values in 
   previous array and increase index position by one. Now sorted array
 
  Index:     0  1  2  3  4  5  6  7  8  9 10   11 12
  Count:     0  1  1  2  2  3  3  4  4  5  6   8  8

Counting Sort Program

public class CountingSort {

public static void main(String[] args) {

//Assuming our key values are with in range 0 - 9
int[] items = { 2, 6, 3, 2, 8, 4, 8, 1, 5, 3, 1, 4, 0};
System.out.println("Before Counting Sorting :");
printArray(items);

//Perform counting sort sort
countingsort(items);

System.out.println("After Count Sorting :");
printArray(items);
}

private static void countingsort(int []items)
{
//create array of size 10 that will have index value as 0-9
//it will create array of size 10 and initialize
//each element with value 0
int []numbers=new int[10];
for(int key:items)
{
//for each match key, index position element
//increase count as 1
numbers[key]+=1;
}

//Now sort values based on keys and repeat
//this key value as per count
int i=0;
for(int key=0; key0)
{
for(int count=1;count<=numbers[key];count++)
{
items[i++]=key;
}
}

}
}

static void printArray(int items[])
{
for (int item:items)
{
System.out.print(item + " ");
}
System.out.println();
}

}

Output

Before Counting Sorting :
2 6 3 2 8 4 8 1 5 3 1 4 0 
After Count Sorting :
0 1 1 2 2 3 3 4 4 5 6 8 8