Counting Sort works by counting the occurrences of each data value. It assumes that there are n data items in the range of 1..k, where k is an integer. The algorithm can then determine, for each input element, the amount of elements less than it. For example if there are 9 elements less than element x, then x belongs in the 10th data position.
countingsort(A[], B[], k)
for i = 1 to k do
C[i] = 0
for j = 1 to length(A) do
C[A[j]] = C[A[j]] + 1
for 2 = 1 to k do
C[i] = C[i] + C[i-1]
for j = 1 to length(A) do
B[C[A[j]]] = A[j]
C[A[j]] = C[A[j]] - 1
Although this may look complicated, it is actually a very simple and clever algorithm.
Array A[ ] stores the initial data to be sorted.
Array C[ ] is used to count the occurrences of the data values
Array B[ ] is used to store the final, sorted, list.
The first for loop initialises C[ ] top zero.
The second for loop increments the values in C[], according to their frequencies in the data.
The third for loop adds all previous values, making C[] contain a cumulative total.
The fourth for loop writes out the sorted data into array B[].
Two of the for loops take O(k) time, and two take O(n) time. An important point to note is that Counting Sort is stable: All elements of the same value will appear in the same order in the output array array that they do in the input array.
Go to Counting Sort demonstration
Help on using the Applet
Back to main Page