Counting sort is a very fast sorting algorithm. Unfortunately it can't be always used because of the initial conditions needed.

Input: A[1...n] with the assumption that 0 <= A[i] <= k for a certain k. If k is too large, the algorithm becomes inefficient in terms either of running time or of memory usage.

Output: B[1...n] sorted.

The counting sort has 4 main steps.

1) Init: the C and B arrays are created, the first of k elements, the second with n elements as we said above. All the elements must be zero.

2) First for loop: we count the occurrence of each value in A, such that C[i] contains the number of occurrences of i in A.

3) Second loop: we sum two-by-two the occurrences. Now each C[i] contains the number of elements in A that are lesser than or equal to i (you can verify by hands how it works, it's pretty easy). Observation: the value i will go in the cell number C[i] or less in the final array.

4) Final loop, distribution step: taking the previous observation, we distribute the elements in the brand new B.

It's easy to see from the code than the running time is O(k+n). In particular, the algorithm stays efficient until k < nlogn.

Counting sort has another property, which it's called stability: the relative order of equal elements is mantained during the sorting. This can seem just a curiosity, but it's useful for another sorting algorithm, radix sort.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

import java.util.Arrays; public class CountingSort { public static void main(String[] args) { int[] v1 = {4, 1, 8, 2, 7, 5, 6, 3, 9, 0}; System.out.println("Before sorting: " + Arrays.toString(v1)); System.out.println("After sorting: " + Arrays.toString(counting(v1))); } public static int[] counting(int[] A) { int k = 10; int[] C = new int[k]; int[] B = new int[A.length]; for (int j = 0; j < A.length; j++) { (C[A[j]])++; } for (int j = 2; j < k; j++) { C[j] = C[j] + C[j-1]; } for (int j = A.length-1; j>=0; j--) { B[C[A[j]]] = A[j]; C[A[j]]--; } return B; } }