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 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. In computer science and mathematics, a sorting algorithm is an algorithm that puts elements of a list in a certain order. ... Bucket sort is a sort algorithm that works by partitioning an array into a finite number of buckets and then sorting each bucket. ... In mathematics, the range of a function is the set of all output values produced by that function. ... This article or section does not cite its references or sources. ... Pigeonhole sorting, also known as count sort, is a sorting algorithm that takes linear time (Θ(n)), which is the best possible performance for a sorting algorithm since one must inevitably look at each of the elements being sorted at least once, regardless of the sorting algorithm. ...

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). In computer science and mathematics, a sorting algorithm is an algorithm that puts elements of a list in a certain order. ... Big O notation or Big Oh notation, and also Landau notation or asymptotic notation, is a mathematical notation used to describe the asymptotic behavior of functions. ...

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 (shifted), so that the minimum value of A matches the smallest index of C. (Translation by subtracting the minimum value of A from each element to get an index into C therefore gives a counting sort. If a more complex function is used to relate values in A to indices into C, it is a bucket sort.) 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). Bucket sort is a sort algorithm that works by partitioning an array into a finite number of buckets and then sorting each bucket. ... In computer science, a selection algorithm is an algorithm for finding the kth smallest (or kth largest) number in a list. ...

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 (again, see bucket sort and pigeonhole sort). 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. Bucket sort is a sort algorithm that works by partitioning an array into a finite number of buckets and then sorting each bucket. ... Pigeonhole sorting, also known as count sort, is a sorting algorithm that takes linear time (Θ(n)), which is the best possible performance for a sorting algorithm since one must inevitably look at each of the elements being sorted at least once, regardless of the sorting algorithm. ... A radix sort is a sorting algorithm that can rearrange integer representations based on the processing of individual digits in such a way that the integer representations are eventually in either ascending or descending order. ...

Because counting sort uses key values as indexes into an array, it is not a comparison sort, the Ω(n log n) lower-bound for sorting is inapplicable. A comparison sort is a particular type of sorting algorithm; a number of well-known algorithms are comparison sorts. ...

The algorithm

Informal

1. Count the discrete elements in the array. (after calculating the minimum and the maximum)
2. Accumulate the counts.
3. Fill the destination array from backwards: put each element to its count^th position.
   Each time put in a new element decrease its count.

C++ implementation

 /// countingSort - sort an array of values. /// /// For best results the range of values to be sorted /// should not be significantly larger than the number of /// elements in the array. /// /// param A - input - set of values to be sorted /// param num_of_elements - input - number of elements in the input and output arrays /// return sorted - new ordered array of the first num_of_elements of the /// input array. caller is responsible for freeing this array. /// int* countingSort(const int A[], const int num_of_elements) { // search for the minimum and maximum values in the input int min = A[0], max = min; for (int i = 1; i < num_of_elements; ++i) { if (A[i] < min) min = A[i]; else if (A[i] > max) max = A[i]; } // create a counting array, counts, with a member for // each possible discrete value in the input. // initialize all counts to 0. int distinct_element_count = max - min + 1; int* counts = new int[distinct_element_count]; // C for (int i = 0; i < distinct_element_count; ++i) counts[i] = 0; // for each value in the unsorted array, increment the // count in the corresponding element of the count array for (int i = 0; i < num_of_elements; ++i) ++counts[ A[i] - min ]; // accumulate the counts - the result is that counts will hold // the offset into the sorted array for the value associated with that index for (int i = 1; i < distinct_element_count; ++i) counts[i] += counts[ i - 1 ]; // store the elements in a new ordered array int* sorted = new int[num_of_elements]; // B for (int i = num_of_elements - 1; i >= 0; --i) // decrementing the counts value ensures duplicate values in A // are stored at different indices in sorted. sorted[ --counts[ A[i] - min ] ] = A[i]; delete[] counts; return sorted; } 

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 0-262-03293-7. 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.

Thomas H. Cormen is the co-author of Introduction to Algorithms, along with Charles Leiserson, Ron Rivest, and Cliff Stein. ... Charles E. Leiserson is a computer scientist, specializing in the theory of parallel computing and distributed computing, and particularly practical applications thereof; as part of this effort, he developed the Cilk multithreaded language. ... Professor Ron Rivest Professor Ronald Linn Rivest (born 1947, Schenectady, New York) is a cryptographer, and is the Viterbi Professor of Computer Science at MITs Department of Electrical Engineering and Computer Science. ... Clifford Stein is a computer scientist, currently working as a professor at Columbia University in New York, NY. He earned his BSE from Princeton University in 1987, a MS from Massachusetts Institute of Technology in 1989, and a PhD from Massachusetts Institute of Technology in 1992. ... Cover of the second edition Introduction to Algorithms is a book by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. ... Donald Ervin Knuth ( or Ka-NOOTH[1], Chinese: [2]) (b. ...

External links

Wikibooks Algorithm implementation has a page on the topic of

Counting sort

• Analyze Counting Sort in an online Javascript IDE
• Demonstration applet
• Counting sort