Input size (n): Maximum key (k):
iInput
(A)		Counts
(C)		 Cumulative
(C)		Output
(B)		   
This page allows you to experiment with counting sort. You can specify the number of items to be sorted ( n = length[A] ) and the maximum key value ( k = length[C] ) in the fields above. The "Initialize" button sets the input to random values and executes the loops that count the number of times each key occurs and the cumulative counts. You can change the input values by typing directly into the input fields; the counts will be recalculated automatically. Each time the "Next Item" button is clicked one more value from the input is inserted into its proper place in the output array. The proper item is marked in the input array with a "-->" and the cumulative count is marked with a "--" prior to being decremented.

Here is the pseudocode from Cormen, Leiserson, Rivest, and Stein:

Counting-Sort(A, B, k)

  1. for i <-- 0 to k
  2.     do C[i] <-- 0
  3. for j <-- 1 to length[A]
  4.     do C[A[j]] <-- C[A[j]] + 1
  5. --> C[i} now contains the number of elements equal to i
  6. for i <-- 1 to k
  7.     do C[i] <-- C[i] + C[i - 1]
  8. --> C[i} now contains the number of elements less than or equal to i
  9. for j <-- length[A] downto 1
  10.     do B[C[A[j]]] <-- A[j]
  11.         C[A[j]] <-- C[A[j]] - 1

Note that the C array is shown twice at left, to make it easier to see how the cumulative values are calculated.