Counting sort is a sorting algorithm which (like bucket sort) takes advantage of knowing the range of the numbers in the array to be sorted (array A). It uses this range 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. It is less efficient than pigeonhole sort.

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 lengths 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 indices of C must run from the minimum to the maximum value in A to be able to index C directly with the values of A. Otherwise, the values of A will need to be translated, so that the minimum value of A matches the smallest index of C. If the minimum and maximum values of A are not known, an initial pass of the data will be necessary to find these (this pass will take time Θ(n); see selection algorithm).

The length of the counting array C must be at least equal to the range of the numbers to be sorted (that is, the maximum value minus the minimum value plus 1). This makes counting sort impractical for large ranges in terms of time and memory needed. Counting sort may for example be the best algorithm for sorting 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 is too large for counting sort to be suitable alone.

Because counting sort uses key values as indexes into an array, it is not a comparison sort, allowing it to break the Ω(n log n) lower-bound on those sorts.

Sample implementations

C

/* end is the last index + 1 */
void csort(int array*, const int end,
      const int max, const int min)
{
  int i;
  const int range = max-min+1;
  int count*,
      scratch*;
  for(i=0; i* = 0;
  /* Set the value of count* to the number of
   * elements in array with value i+min-1. */
  for(i=0; i*+1-min;
    count*++;
  }
  /* Update count* to be the number of
   * elements with value less than i+min. */
  for(i=1; i+ = count[i-1;
  /* Copy the elements of array into scratch in
   * stable sorted order. */
  for(i=(end-1); i>=0; i--) {
    int c = array*-min;
    int s = count*;
    scratch= 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*++;
  }
  for(i=0; i= scratch[i;
}

Visual Basic

(Note: Code includes setup and performance timers. To accommodate Visual Basic, avoid negative index numbers and use of reserve words the value of xend has been sustituted in place of xmin in certain calculations and most variable names have been changed.)

Option Explicit '-- Counting sort

RESULTS: (Counting sort - Visual Basic)

1.) Total number of items sorted:.......................... 9,900,000

2.) Total Array (array) size to accommodate the sort:...... 9,999,999

3.) Total Count (array) size to accommodate the sort:...... 9,899,999

4.) Total Scratch (array) size to accommodate the sort:.... 9,900,000

5.) Total length of key:................................... 7 decimal digits.

6.) Total time for setup .................................. 3.54699999999965 seconds.

7.) Total time for sort.................................... 16.219000000001 seconds.

Class Determination

External links

• Demonstration applet

References

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0262032937. Section 8.2: Counting sort, pp.168–170.
• Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Second Edition. Addison-Wesley, 1998. ISBN 0-201-89685-0. Section 5.2, Sorting by counting, pp.75–80.
• Seward, Harold H. Information sorting in the application of electronic digital computers to business operations Masters thesis. MIT 1954.

Sort algorithms | Stable sorts

Countingsort | Laskentalajittelu | Tri comptage | מיון מנייה | Counting sort | Counting sort | Sortowanie przez zliczanie | Сортировка подсчётом