Counting sort

Counting Sort - a sorting algorithm which takes advantage of knowing the maximum value within the array to be sorted and uses this to create an array (referenced by the values within the array to be sorted) that will serve to count the number of values of a certain number and, after this, the future positions of the values on a third array, which is the sorted permutation of the second array (i.e., A[i] <= A[j], i < j). This algorithm is stable and it is O(n+k), where k is the maximum value within the array. In order for this algorithm to have any semblance of efficiency, k must be comparatively small. The values within an array have to be known and non-negative.

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.