Counting sort is a sorting algorithm which (like bucket sort) takes advantage of knowing the maximum possible value within the array to be sorted (array A). It uses this maximum value to create an array C of this length. Each index i in array C is then used to count how many elements in A that have a value less than i. The counts stored in C can then be used to put the elements in A into their right position in the resulting sorted array.

Characteristics of counting sort

Counting sort is stable (see sorting algorithm) and has a running time of Θ(n+k), where n and k are the length of the arrays A (the input array) and C (the counting array), respectively. In order for this algorithm to be efficient, k must not be too large compared to n. As long as k is O(n) the running time of the algorithm is Θ(n).

The values within the original array have to be nonnegative integers of a known range. If the maximum value in the array is not known an initial pass of the data will be necessary to find the largest value (this pass will take time Θ(n)). Possible negative values can be adjusted for by finding the minimum value in the array. When indexing value x into array C, x minus the minimum value can then be used as the index.

The length of the counting array C must be at least equal to the range of the numbers to be sorted (that is, maximum value minus minimun value plus 1). This makes counting sort impractical for large ranges of numbers in terms of time and memory needed. Counting sort may for example be the best algorithm to sort numbers whose range is between 0 and 100, but it is probably unsuitable for sorting a list of names alphabetically. However counting sort can be used in radix sort to sort a list of numbers whose range are too large for counting sort to be suitable alone.

Sample implementations

C

/* end is the last index + 1 */
void 
csort(int array[], const int end,
      const int max, const int min)
{
  int i,j;
  const int range = max-min+1;
  int count[range],
      scratch[end];

  for(i=0; i<range; i++)
    count[i] = 0;

  /* Set the value of count[i] to the number of
   * elements in array with value i+min-1. */
  for(i=0; i<end; i++) {
    int c = array[i]+1-min;
    count[c]++;
  }

  /* Update count[i] to be the number of
   * elements with value less than i+min. */
  for(i=1; i<range; i++)
    count[i] += count[i-1];

  /* Copy the elements of array into scratch in
   * sorted order. */
  for(i=0; i<end; i++) {
    int c = array[i]-min;
    int s = count[c];
    scratch[s] = array[i];
    /* Increment count so that the next element
     * with the same value as the current element
     * is placed into its own position in scratch. */
    count[c]++;
  }

  for(i=0; i<end; i++)
    array[i] = scratch[i];
}

References:

• Cormen, et al. Introduction to Algorithms 2nd. ed. 2001. The MIT Press.
• Seward, Harold H. Information sorting in the application of electronic digital computers to business operations Masters thesis. MIT 1954.