In this tutorial, we are going to learn about counting sort in detail and its algorithmic implementation.

Counting Sort

• Not an in-place algorithm.
• O(n) - can achieve this because we’re making assumptions about the data we’re sorting.
• If we want the sort to be stable, we have to do some extra steps.
• Makes Assumptions about the data.
• Doesn’t use comparisons.
• Counts the number of occurrences of each value.
• Only works with non-negative discrete values(cant work with floats, Strings).
• Values must be within a specific range.

1. Assume we have values between 1 to 10 inclusive.
2. We have 10 possible values, so we create a counting array of length 10.
3. Traverse the input array from left to right.
4. Use the counting array to track how many of each value are in the input array.
5. Using the counts in the counting array, write the values in sorted order to the input array.

Counting Sort Algorithm

1. countingSort(array, size)
2. max <- find largest element in array
3. initialize count array with all zeros
4. for j <- 0 to size.
   find the total count of each unique element and store the count at jth index in count array
5. for i <- 1 to max.
   find the cumulative sum and store it in count array itself
6. for j <- size down to 1.
   restore the elements to array decrease count of each element restored by 1.

Counting Sort Programmatic Implementation in Java

public class CountingSort {
	public static void main(String[] args) {
		int[] intArray = { 2, 5, 9, 8, 2, 8, 7, 10, 4, 3 };

		countingSort(intArray, 1, 10);

		for (int i = 0; i < intArray.length; i++) {
			System.out.print(intArray[i]+ " ");
		}
	}

	public static void countingSort(int[] input, int min, int max) {

		int[] countArray = new int[(max - min) + 1];

		for (int i = 0; i < input.length; i++) {
			countArray[input[i] - min]++;
		}
		int j = 0;
		for (int i = min; i <= max; i++) {
			while (countArray[i - min] > 0) {
				input[j++] = i;
				countArray[i - min]--;
			}
		}
	}
}

Output:

2 2 3 4 5 7 8 8 9 10