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.

The pseudocode Counting Sort algorithm is as follows:

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