• Assume the elements in the array are in a small range
• O(n+k), memory complexity O(n+k), n is the number of elements, range 0 to k is the range of elements

public class Counting
{
	public static void countingSort(int [] A, int [] B, int k)
	{
		int [] C = new int[k+1];

		for(int i = 0, len = A.length; i < len; i++)
			C[A[i]] += 1;

		for(int i = 1; i <= k; i++)
			C[i] = C[i] + C[i-1];

		for(int i = A.length-1; i >= 0; i--)
		{
			B[C[A[i]]-1] = A[i];
			C[A[i]] -= 1;
		}

		display(C);
		display(B);
	}

	public static void display(int [] array)
	{
		for(int e : array)
			System.out.printf("%5d", e);
		System.out.println();
	}

	public static void main(String args[])
	{
		int [] A = {2, 5, 3, 0, 2, 3, 0, 3};
		int [] B = new int[A.length];

		countingSort(A, B, 5);
	}
}
			

• CLRS Chapter 8